Partitions Sum

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

对于任意的正整数N,可以将它表示成若干无序正整数之和。

比如N = 5

5 = 1 + 1 + 1 + 1 + 1

5 = 1 + 1 + 1 + 2

5 = 1 + 1 + 3

5 = 1 + 2 + 2

5 = 1 + 4

5 = 2 + 3

5 = 5

对于N的每种表示,我们给它定义一个价值:即任意一对数的最大公约数之和。比如5 = 1 + 2 + 2,价值为gcd(1,2) + gcd(1,2) + gcd(2,2) = 4,对于5 = 5,价值为0

现在问你,对于N,它的所有表示价值和是多少? 比如N = 5的时候,价值和为 10 + 6 + 3 + 4 + 1 + 1.

由于sweetzero不喜欢一些数字,因此对于N的表示,他只对那些没有包含他不喜欢的数字的表示的价值感兴趣。由于他太懒了,因此他想请您帮忙求出他感兴趣的N的表示的价值和吧。

Input

多组数据,对于每组数据

第一行两个正整数N,M (1 <= N <= 2000, 0 <= M <= N)

第二行有M个范围为[1,N]的正整数,表示sweetzero不喜欢的数字

(不超过100组数据,N >= 500的数据约为15%)

Output

对于每组数据,输出sweetzero感兴趣的N的表示的价值之和 % 1000000007

Sample Input

5 0
5 1
1
5 1
2

Sample Output

25
1
14

Source

sweetzero

Manager

Information
Solved Number14
Submit Number75
Problem Tags
dp
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel