Description

LYK最近在研究整数拆分问题。他认为一个数字可以被拆分成若干正整数之和。例如当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

对于其中一种拆分方式，所产生的价值为其中每一对数的 gcd之和。

例如5=1+2+2，它所产生的价值为gcd(1,2)+gcd(1,2)+gcd(2,2)=4。

对于5=5这种拆分方式，产生的价值为0。

当然LYK也有部分不喜欢的数，它想知道对于所有拆分方式中没有它不喜欢的数的拆分中

产生的价值之和对1000000007 取模后的结果是多少。

Format

若干组数据，不超过 5组。对于每组数据，第一行一个数 n。接下来一行第一个数 m，表示有 m 个 LYK 不喜欢的数字，紧接着 m 个数，表示 LYK 不喜欢的数字。

n<=2000。

输出若干行表示答案。

5 
0