Problem Background

MLE the Great once said:

To address this situation, we have established the Urban Development Committee.

Problem Description

In high school campuses, we often see randomly appearing couples. Their emotions are too profound for OIers to understand, even retired AzureHair couldn't comprehend this behavior. However, as a member of the self-proclaimed Urban Development Committee, he has his own method of understanding.

He believes that girls are usually very strict with boys. At the beginning of the day, the boy's score in the girl's heart increases by $1$, and if he annoys her $x$ times that day, the score decreases by $x$ on top of that. The score accumulates, and if it ever drops to $0$ or below, it could lead to severe urbanization consequences.

Now, William is engaging in an urbanization activity with Chtholly. With the help of Nahida, William has acquired superpowers: one is that he can foresee the score changes for the upcoming cycle, with an initial cycle length of $n$; the other is that he can choose to start from any day, and the days before the start will be appended after the last day.

After trying starting from each day, he found $a$ starting dates that would prevent him from being urbanized. He then concatenates these sequences in order of their starting dates, forming a cycle of length $a$ times the original. He repeats this operation $k$ times. Since trying day by day is too tiring, William just wants to know how many starting dates will keep him from being urbanized after the last operation, modulo $998244353$.

Formally, we call a sequence "safe" if its prefix sum is always greater than $0$.

For a sequence $A_i$ of length $n$, construct the sequence $A_{i+1}$ according to the following algorithm, initially empty.

• Repeat $n$ times:

1. If $A_i$ is safe, append it to the end of $A_{i+1}$.

2. Rotate $A_i$ left by one position, i.e., let $A_{i_j} \leftarrow A_{i_{j+1 \mod n}}$.

Given $A_0$, which satisfies that each element is no greater than $1$.

Starting from $A_0$, generate sequences $A_1$ to $A_{k+1}$ according to the above rules. Request the length ratio of $A_{k+1}$ to $A_k$, which is always an integer if it exists. Output this value modulo $998244353$. Specifically, if $A_k$ is empty, output 0.

Input Format

Input Format

Normal problem statement:

Two lines. The first line contains two integers $n$ and $k$, representing the initial cycle length and the number of operations.

The second line contains $n$ integers, each no greater than $1$, representing the daily score changes.

Formal problem statement:

Two lines. The first line contains two integers, the length of $A_0$ $n$ and $k$.

The second line is $A_0$.

Output Format

One line containing an integer, the answer modulo $998244353$.

Sample Input and Output

Sample Input #1

8 0
1 1 -2 1 1 -1 0 1

Sample Output #1

2

Sample Input #2

6 0
1 1 -4 -5 1 -4

Sample Output #2

0

Notes/Hints

[Sample Explanation 1]

For the data in Sample #1, the initial cycle is 1 1 -2 1 1 -1 0 1. The sequences starting from each day are:

1 1 -2 1 1 -1 0 1
1 -2 1 1 -1 0 1 1
-2 1 1 -1 0 1 1 1
1 1 -1 0 1 1 1 -2
1 -1 0 1 1 1 -2 1
-1 0 1 1 1 -2 1 1 
0 1 1 1 -2 1 1 -1
1 1 1 -2 1 1 -1 0

Only the sequences starting from the 4th and 8th days are valid.

Formal problem statement:

$A_1 = \{1,1,-1,0,1,1,1,-2,1,1,1,-2,1,1,-1,0\}$, with a length of 16, hence the output is 2.

[Sample Explanation 2]

It can be proven that no valid solution exists.

Hey! All samples have $k=0$, isn't that too much?!

Data Range:

For $15\%$ of the data, $1 \le n \le 10$, $1 \le k \le 5$.

For another $25\%$ of the data, $k = 0$.

For $100\%$ of the data, $1 \le n \le 10^6$, $0 \le k \le 10^6$, $-10^9 \le A_{0_i} \le 1$.

见题面 Input 部分

见题面 Output 部分