Urbanization Safety

In a high‐school campus one often sees couples whose interactions refresh randomly. William is about to engage in a kind of "urbanization" with Kotori. In this process, each day is assigned an integer score that changes the "emotional balance". In particular, for a period of n days the score changes are known. Initially, in a girl’s heart the score increases by 1 at the start of the day, but every time the boy upsets her the score decreases by 1. (If he upsets her x times in a day then the net change for that day is 1-x.) The cumulative score keeps accumulating over the period, and if at any moment the cumulative score becomes less than or equal to 0, then drastic "de-urbanization" will occur.

Formally, we call a sequence A = [a₀, a₁, …, a_n-1] safe if its shifted prefix sums are all strictly positive. That is, if there exists an ordering of the days (by a cyclic shift) such that, when letting

$$P(i)=\sum_{j=0}^{i-1}b_j\quad (1\le i\le n),$$

we have $$P(i)>0\quad \text{for all }1\le i\le n.$$

William has the power to see the score change for the coming period of n days – his initial sequence, denoted by A₀. Moreover, he can choose any day to start his urbanization and, before that day, the days are appended to the end of the period. In other words, he is allowed to cyclically rotate the sequence.

For any sequence A_i of length n, define the following process to construct the new sequence A_i+1:

1. Repeat the following exactly n times:
   1. If the current sequence (i.e. the current rotation of A_i) is safe, append the entire sequence to the end of A_i+1.
   2. Cyclically rotate A_i to the left by one position.

Thus, if we let f(X) denote the number of starting positions (cyclic rotations) of a sequence X that result in a safe sequence, then the length of A_i+1 is

$$|A_{i+1}| = f(A_i) \cdot |A_i|.$$

Initially, William is given a sequence A₀ of length n, with the guarantee that each element is at most 1. He then applies the above process for k rounds. Finally, he wishes to know the ratio $$\frac{|A_{k+1}|}{|A_k|},$$

which, if defined, is always an integer. Since the answer can be huge, output it modulo 998244353. Note that if A_k is empty then you should output 0.

Remark: It can be shown that the safety property of a sequence is cyclic in nature and in fact the number of safe rotations of a safe sequence is determined by its structure. In this problem the key observation is that if we denote the number of safe rotations for A₀ by c (i.e. f(A₀) = c), then for every subsequent round (provided the sequence is nonempty) the ratio always equals c raised to some power. In particular, one may prove that

$$\frac{|A_{k+1}|}{|A_k|} = c^{k+1},$$

so the answer is c^(k+1) mod 998244353 (with the convention that if c = 0 then the answer is 0).

---

Input Format: The first line contains two integers n and k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 10^9). The second line contains n integers a0, a1, …, an-1 representing the score changes, with each ai ≤ 1 (and they may be negative).

Output Format: Output a single integer — the value of c^(k+1) mod 998244353, where c is the number of rotations of A₀ that are safe. If no rotation of A₀ is safe (so that A_k is empty) output 0.

inputFormat

The first line contains two integers n and k.

The second line contains n integers a0, a1, …, an-1 separated by spaces.

outputFormat

Output a single integer — the ratio |A_(k+1)|/|A_k| mod 998244353.

sample

2 1
1 1

4