G. Games
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an integer sequence $$$A_1,A_2,\ldots,A_N$$$ and an integer $$$K$$$.

You'll prepare $$$K$$$ piles of stones. Each pile should contain exactly $$$A_i$$$ piles for some $$$i$$$. All piles are distinguishable; there are $$$N^K$$$ different configurations.

You and Mike will play a game with the piles. You and Mike alternately do the following operation, with you going first.

  • Choose at most $$$6$$$ piles (choosing $$$0$$$ piles is not allowed) and remove an arbitrary positive number of stones from each of the chosen piles. Note that the player can remove different numbers of stones from different piles.

The player who cannot make a valid move loses. Assuming both players play optimally, count the number of initial configurations that result in your loss, modulo $$$998244353$$$.

Input

The first line contains integers $$$N$$$ ($$$1 \leq N \leq 100$$$) and $$$K$$$ ($$$1 \leq K \leq 10^{18}$$$).

The second line contains integers $$$A_1,A_2,\ldots,A_N$$$ ($$$1 \leq A_1 \lt A_2 \lt \cdots \lt A_N \leq 100$$$).

Output

Print the answer.

Examples
Input
1 7
1
Output
1
Input
5 100
2 3 5 7 9
Output
842434993