시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 1024 MB 3 3 3 100.000%

문제

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$.

입력

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 < A_2 < \cdots < A_N \leq 100$).

출력

Print the answer.

예제 입력 1

1 7
1

예제 출력 1

1

예제 입력 2

5 100
2 3 5 7 9

예제 출력 2

842434993