Given $k$ and a sequence of coefficients $w_0, \dots, w_{2^{k-1}-1}$. The weight of a permutation $p$ of order $n \ge k$ is defined as $$ \text{val}(p) = \prod_{i=1}^{n-k+1} w_{f(p_i, p_{i+1}, \dots, p_{i+k-1})} $$ where $$ f(a_1, a_2, \dots, a_k) = \sum_{i=1}^{k-1} 2^{i-1} [a_i < a_{i+1}] $$ Given $n$, calculate the sum of weights of all permutations of order $n$ modulo $998244353$.
Input
The first line contains two integers $n$ and $k$.
The second line contains $2^{k - 1}$ integers, where the $i$-th integer represents $w_{i-1}$.
Output
Output a single integer representing the answer modulo $998244353$.
Examples
Input 1
3 2 1 2
Output 1
13
Input 2
5 3 1 2 3 4
Output 2
1875
Input 3
6 4 1 2 3 4 5 6 7 8
Output 3
68850
Constraints
This problem uses bundled testing. You must pass all test cases in a subtask to receive the points for that subtask.
| Subtask ID | $n \le$ | $k =$ | Score |
|---|---|---|---|
| $1$ | $10$ | $4$ | $5$ |
| $2$ | $20$ | $4$ | $10$ |
| $3$ | $10^5$ | $2$ | $5$ |
| $4$ | $100$ | $3$ | $10$ |
| $5$ | $4000$ | $3$ | $10$ |
| $6$ | $4 \times 10^4$ | $3$ | $15$ |
| $7$ | $10^5$ | $3$ | $5$ |
| $8$ | $2000$ | $4$ | $10$ |
| $9$ | $4 \times 10^4$ | $4$ | $10$ |
| $10$ | $10^5$ | $4$ | $20$ |
For all data: $2 \le k \le 4$, $k \le n \le 10^5$, $0 \le w_i < 998244353$.