Problem B: 硬币兑换三

Memory Limit：256 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：201 Solved：56

Description

给一个整数数组coins表示不同面额的硬币，另外给一个整数表示总金额。请你计算并返回可以用这些面值凑成指定总金额的不同方法数量，输出总数除以1000000的余数。如果没有任何办法凑出总金额，则输出0。



Input

输入第一行为两个整数n, target，n表示有多少种不同面值，target表示需要组合成的总数。
第二行为n个整数分别代表硬币的面值。

Output

输出凑出不同组合的总数除以1000000的余数。如果任何组合都无法凑出，则输出0。

Sample Input Copy 

3 5
1 2 5

Sample Output Copy 

4

HINT

硬币数量n不超过200种，需要凑的总数不超过1500000。