城市化发展委员会
题目背景
MLE 大帝曾说过：
所以为了应对这种情况我们设立了**城市化发展委员会**。
题目描述
在高中的校园里我们常常能看到随机刷新的小情侣，对于他们之间的情感，对于 OIer 来说还是太过于高深了，即使是退役的 AzureHair 也无法理解这一行为，但是作为自命的城市化发展委员会的常委，他有自己的一套理解方法。
他认为，女生往往对男生十分的严格。一天开始时男生在女生的心里的积分会加 $1$，而如果当天惹女生生气了 $x$ 次，积分就会在此基础上减 $x$。积分会不断累计，一旦小于等于 $0$ 就可能导致去城市化的严重后果。
现在 **威廉** 在和 **珂朵莉** 进行一种城市化行为，**威廉** 在~~纳西妲~~的帮助之下获得了超能力：一是他可以预知到接下来一个周期的积分变化情况，初始的周期长度为 $n$；二是他可以选择从任意一天开始，开始前的日子将会被拼接到最后一天之后。
他从每一天开始都尝试过一次后，发现了 $a$ 个能使得他不被去城市化的起始日期。随后他会将这若干种情况下的序列按照起始日期的先后拼在一起，变成一个长度为原先 $a$ 倍的周期。他如此重复操作 $k$ 次，由于一天天地试太累了，**威廉** 只想知道最后一次操作后有多少个起始日期能让自己不被去城市化，对 $998244353$ 取模。
---
形式化地说，我们称满足前缀和始终大于 $0$ 的数列为 “安全的”。
对于一个长为 $n$ 的数列 $A_i$，根据以下算法构造出数列 $A_{i+1}$，初始时 $A_{i+1}$ 为空。
- 重复执行 $n$ 次：
1. 若 $A_i$ 是安全的，将其整个接到 $A_{i+1}$ 末尾。
2. 将 $A_i$ 循环左移一位，即令 $A_{i_j} ← A_{i_{j+1 \bmod n}}$。
现在给定 $A_0$，**满足其各项均不大于 1**。
从 $A_0$ 开始按上述规则生成数列 $A_1$ 到 $A_{k+1}$，请求出 $A_{k+1}$ 与 $A_k$ 的长度比，这个值只要存在就一定是整数，请输出它对 $998244353$ 取模的值。特别地，如果 $A_k$ 为空，请输出 ```0```。
输入输出格式
输入格式
普通题意：
共两行，第一行两个整数 $n$ 和 $k$，表示初始的周期长度和操作次数。
第二行 $n$ 个小于等于 1 的整数，表示每天的积分变化。
形式化题意：
共两行，第一行两个整数为 $A_0$ 的长度 $n$ 以及 $k$。
第二行是 $A_0$。
输出格式
一行一个整数，表示答案对 $998244353$ 取模的结果。
输入输出样例
输入样例 #1
8 0
1 1 -2 1 1 -1 0 1输出样例 #1
2输入样例 #2
6 0
1 1 -4 -5 1 -4输出样例 #2
0说明
**【样例解释1】**
对于样例 #1 的数据，初始周期为 ```1 1 -2 1 1 -1 0 1```。从每一天开始得到的序列分别是：
```text
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
```
只有从第 4 天和第 8 天开始的序列是满足条件的。
形式化题意：
$A_1=\{1,1,-1,0,1,1,1,-2,1,1,1,-2,1,1,-1,0\}$，长度为 16，因此应输出 2。
**【样例解释2】**
可以证明不存在合法的方案。
喂！样例全都 $k=0$ 是不是太过分了？！
**数据范围：**
对于 $15\%$ 的数据，保证 $1\le n \le 10$，$1\le k \le 5$。
对于另外 $25\%$ 的数据，保证 $k=0$。
对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$0 \le k \le 10^6$，$-10^9 \le {A_0}_i \le 1$。