问题描述：

给定N个正整数，和一个数M，要求从这N个数中选出一些数来求和，使和为M的整数倍，问一共有多少种方法。
0≤M,N≤1000

输入：

第一行两个数表示N和M；
第二行N个数 分别表示给定的这N个数。

输出：

一个整数，表示方法总数对1234567的余数
不考滤N个数中的相同数引起的重复。

样例

输入

3 2
2 2 4

输出

7

备注

可以有{2}，{2}，{4}，{2，4}，{2，4}，{2，2}，{2，2，4} 共7种方法。