题目内容

塔子哥是一个喜欢玩扑克牌的人，他经常和朋友们一起玩各种有趣的扑克牌游戏。他最近学会了一个新的游戏，叫做“整除游戏”。这个游戏的规则是这样的：

系统会随机发 $n+1$ 张牌，每张牌上都有一个正整数，不一定是扑克牌上的数字。第一张牌给塔子哥，后 $n$ 张牌按照发牌顺序排成连续的一行，让塔子哥看到。然后，系统会问塔子哥一个问题：后 $n$ 张牌中，是否存在连续的若干张牌，其和可以整除塔子哥手中牌上的数字？塔子哥需要回答 1 或者 0 ，表示是或者否。

如果塔子哥回答正确，他就可以赢得这些牌，并且可以继续玩下一轮。如果塔子哥回答错误，他就会输掉手中的牌，并且游戏结束。塔子哥想要玩得越久越好，赢得越多越好。所以，他想知道，在每一轮中，他应该如何判断后 $n$ 张牌中是否存在满足条件的连续若干张牌。

输入描述

输入数据可能有多组。

每组输入数据有两行，输入到文件结尾结束。

输入第一行为两个整数 $n$ 和 $m$ ，空格隔开。 $m$ 代表发给塔子哥牌上的数字

输入第二行为 $n$ 个整数，代表后续发的 $n$ 张牌上的数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

$1\le n \le 1000$ ， $1\le a_i \le 400000$ ， $1\le m \le 1e8$ 。

输入保证数据不会对于 $1000$ 组，并且保证用例合法。

输出描述

对每组输入，如果存在满足条件的连续若干张牌，则输出 1 ，否则，输出 0 。

样例

输入

6 7
2 12 6 3 5 5
10 11
1 1 1 1 1 1 1 1 1 1

输出

1
0

样例解释

两组输入。

第一组塔子哥牌的数字为 $7$ ，再发了 $6$ 张牌。第 $1、2$ 两张牌数字和为 $14$ ，可以整除 $7$ ，输出 $1$ 。

第二组塔子哥牌的数字为 $11$ ，再发了 $10$ 张牌，这 $10$ 张牌数字和为 $10$ ，无法整除 $11$ ，输出 $0$ 。

思路:取模

由小学数学，我们知道数组中一个子段$[l,r]$是$m$的倍数 , 当且仅当 $(a_l + ... + a_r) \% m = 0$

那么将其转化成前缀和的形式，就是$(s_r - s_{l-1}) \% m = 0$

也就是$s_l \% mod = s_r \% mod$

所以我们求一下前缀和，看有没有$i,j , i \neq j$ 使得$s_i = s_j$ 的。有输出1,没有输出0