有$n$个正整数排成一行。你的目的是要从中取出一个或连续的若干个数，使它们的和能够被$k$整除。 例如，有$6$个正整数，它们依次为$1、2、6、3、7、4$。若$k=3$，则你可以取出$1、2、6$，或者$2、6、3、7$，也可以仅仅取出一个$6$或者$3$使你所取的数之和能被$3$整除。当然，满足要求的取法不止以上这$4$种。事实上，一共有$7$种取法满足要求。 给定$n$和$k$，以及这$n$个数。你的任务就是确定，从这$n$个数中取出其中一个数或者若干连续的数使它们的和能被$k$整除有多少方法。 由于取法可能很多，因此你只需要输出它模$1234567$的值即可。

第一行有两个正整数，分别代表$n$和$k$。输入数据保证有$n \le 500000，k \le 100000$。
以下$n$行每行一个正整数。这些正整数保证都不大于$10000$。

一个正整数。它应该是你的答案$\bmod 1234567$的结果。

6 3
1
2
6
3
7
4 · \n
 \n
 \n
 \n
 \n
 \n
 \n

7 \n