题目背景

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$ 取模的结果。

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

2

6 0
1 1 -4 -5 1 -4

0

提示

【样例解释1】

对于样例 #1 的数据，初始周期为 1 1 -2 1 1 -1 0 1。从每一天开始得到的序列分别是：

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