题目描述

有 \(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\) 整除有多少方法。由于取法可能很多，因此你只需要输出它 \(mod\) \(1234567\) 的值即可。

格式

输入格式

第一行有两个正整数，分别代表 \(n\) 和 \(k\)。
以下 \(n\) 行每行一个正整数。这些正整数保证都不大于 \(10000\)。

输出格式

一个正整数。它应该是你的答案 \(mod\) \(1234567\) 的结果。

样例1

样例输入1

6 3
1
2
6
3
7
4

样例输出1

7

限制

\(100\%\) 的数据：\(n≤500000，k≤100000\)。