说明

在幻想之地，有一群可爱的生物，它们排成了一行，每个生物有一个正整数的属性值。这些生物们很喜欢玩一个有趣的游戏，游戏的规则是取出一些相邻的生物，使它们的属性值之和能够被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≤500000，k≤100000。

以下n行，每行包含一个正整数，表示每个生物的属性值。这些正整数保证都不大于10000。

输出格式：

一个整数，表示你的答案对1234567取模的结果。

样例：

输入：

6 3
1
2
6
3
7
4
    

输出：

7
    

数据范围与提示：

前20%: n≤100

前50%: n≤10000

100%: n≤500000

前缀和为1,3,9,12,19,23

区间[1,2]和为3-0=3

区间[1,3]和为9-0=9

区间[1,4]和为12-0=12

区间[2,5]和为19-1=18

区间[3,3]和为9-3=6

区间[3,4]和为12-3=9

区间[4,4]和为12-9=3

样例