Given an integer sequence $a_0, a_1, \dots$ that satisfies the following linear recurrence relation:

$$\forall i \geq n, a_i \equiv \sum_{k=1}^n c_ka_{i-k} \pmod {998\,244\,353}$$

Given $a_0, a_1, \dots, a_{n-1}$, $c_1, c_2, \dots, c_n$, and $k$, you want to calculate the value of $a_k$ modulo $998\,244\,353$.

Input

The first line contains two integers $n$ and $k$.

The next line contains $n$ integers $a_0, a_1, \dots, a_{n-1}$.

The next line contains $n$ integers $c_1, c_2, \dots, c_n$.

Output

Output a single integer representing the answer.

Examples

Input 1

3 10
2 5 3
1 4 6

Output 1

58953

Input 2

5 75789123
4 6 1 3 8
2 5 0 0 9

Output 2

71403842

Input 3

6 1999999
2 3 4 5 6 7
0 0 0 0 0 0

Output 3

0

Subtasks

For all data, $1 \leq n \leq 10^5$, $0 \leq k \leq 10^9$, and $0 \leq a_i, c_i < 998\,244\,353$.