【题目描述】

给定$n$个正整数，需要从中取出连续的若干个数（可以只取一个数），使得取出的数的总和是$k$的倍数。

请你根据输入，计算一共有多少种不同的取法，答案对$1234567$取余数。

【输入格式】

第一行两个空格隔开的整数，分别表示$n$和$k$。

接下来$n$行，每行一个正整数，表示给定的$n$个正整数。

【输出格式】

输出一个正整数，表示答案对$1234567$取余数的结果。

4 2
1
2
3
4

4

10 6
9
1
69
11
25
33
63
36
37
38

10

【样例解释】

在样例1中，四个数分别为$1,2,3,4$，可以选择取出$\{2\}$，$\{4\}$，$\{1,2,3\}$，$\{1,2,3,4\}$，共$4$种取法。

【数据规模与约定】

对于20%的数据，保证 $1\le n\le100$。

对于40%的数据，保证 $1\le n\le1000$。

对于100%的数据，保证$1\le n\le 10^{5},1\le k \le 10^5$，输入的所有数字均在$10^9$范围内。