Background

The Great Emperor MLE once said:

So, to deal with this situation, we established the Urbanization Development Committee.

Problem Description

On a high school campus, we often see randomly appearing young couples. Their feelings are still too deep for OIers. Even the retired AzureHair cannot understand this behavior. However, as a standing member of the self-proclaimed Urbanization Development Committee, he has his own way to interpret it.

He believes that girls are often very strict with boys. At the start of each day, the boy’s score in the girl’s mind increases by $1$. If he makes her angry $x$ times that day, the score decreases by $x$ on top of that. The score keeps accumulating, and once it becomes $\le 0$, it may lead to the serious consequence of de-urbanization.

Now William is doing a kind of urbanization behavior with Chtholly. With the help of Nahida, William gains superpowers: first, he can foresee the score changes for the next cycle, whose initial length is $n$; second, he can choose to start from any day, and the days before that will be appended after the last day.

After trying starting from every day once, he finds $a$ starting days that can keep him from being de-urbanized. Then he concatenates the sequences of these cases in the order of their starting days, forming a new cycle whose length is $a$ times the original. He repeats this operation $k$ times. Since trying day by day is too tiring, William only wants to know, after the last operation, how many starting days can keep him from being de-urbanized, modulo $998244353$.

Formally, we call a sequence “safe” if all its prefix sums are always greater than $0$.

For a sequence $A_i$ of length $n$, construct a sequence $A_{i+1}$ using the following algorithm. Initially, $A_{i+1}$ is empty.

• Repeat $n$ times:

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

2. Cyclically left shift $A_i$ by one position, i.e. set $A_{i_j} \leftarrow A_{i_{j+1 \bmod n}}$.

Now given $A_0$, with every element not greater than 1.

Starting from $A_0$, generate sequences $A_1$ to $A_{k+1}$ according to the rules above. Please find the length ratio of $A_{k+1}$ to $A_k$. If this value exists, it must be an integer. Output its value modulo $998244353$. In particular, if $A_k$ is empty, output 0.

Input Format

Plain statement:

There are 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 not greater than $1$, representing the daily score changes.

Formal statement:

There are two lines. The first line contains two integers: the length $n$ of $A_0$ and $k$.

The second line is $A_0$.

Output Format

One line with one integer, representing the answer modulo $998244353$.

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

2

6 0
1 1 -4 -5 1 -4

0

Hint

[Sample Explanation 1]

For sample #1, the initial cycle is 1 1 -2 1 1 -1 0 1. The sequences obtained by 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 day 4 and day 8 satisfy the condition.

Formal statement:

$A_1=\{1,1,-1,0,1,1,1,-2,1,1,1,-2,1,1,-1,0\}$, with length 16, so the output should be 2.

[Sample Explanation 2]

It can be proven that no valid solution exists.

Hey! Isn’t it too much that all samples have $k=0$?!

Constraints:

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

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

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

Translated by ChatGPT 5