Alice and Bob

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Alice和Bob玩了无数局博弈觉得有点枯燥,于是他们想买一台售价为n元的switch,在switch上一较高下。他们东拼西凑出了m种面额的钱币,每种面额的钱币有无限张,问凑出n元的方案数。

当n=4时,我们认为{1,1,2},{1,2,1},{2,1,1}为同一种方案。

Input

输入有多组,以EOF为结束。
每一组数据输入长度不超过50位的实数n(1$\le$n$\le$500)整数m(1$\le$m$\le$30),n为switch的价钱,m为钱币的种类。
下一行输入m个带有一位小数的实数或整数ai(0$<$ai$\le$50),表示每种钱币的价值(单位为元)。

Output

对于每组数据输出方案数,结果可能很大,答案对1000000007取模。

 

Sample Input

10 1
1.0
0.3 2
0.1 0.2

Sample Output

1
2

Hint

样例1:

n为10,只有1元的钱币,显然只有一种凑钱方案。

样例2:

n为0.3,有0.1元和0.2元的钱币,有{0.1,0.2}和{0.1,0.1,0.1}这两种方案。

Source

MLE_kenan