#889. 除除除

除除除

Description

我们定义一种操作是将一个正整数n(n>1)用某个整数d替换,这个数必须是n的约数(1≤d≤n)。给你一个正整数n,

你需要确定操作进行的期望次数,如果我们希望不断地使用这种操作来将n变成1,假设每次操作选择每个可能的d

的概率均等。为了便于计算,输入将给出n和它的所有不同质因数p_1,p_2,?p_m,保证n恰好有m个不同的质因数。

为了便于输出,设答案是有理数a/b,并且有bc≡1(mod10^9+7),你只需要输出ac对10^9+7取模的值。例如当n=351

384000时,期望运算的次数为

1384855049944986283970053414177036273994739277918823/282971529872677632598150446595770345000925504317000≈4.893973081

但你只需要输出321468106即可。

Format

Input

输入包含多组测试数据,以EOF结束。

对于每组测试数据:

第一行包含两个正整数n和m,其中m表示n的不同质因数个数,满足2≤n≤10^24。

第二行包含m个质数p_1,p_2,...,p_m,对于i=1,2,...,m满足2≤p_i≤10^6。

约200000组数据。

Output

对于每组测试数据,输出一行一个整数,表示题目要求输出的值。

Samples

2 1
2
4 1
2
6 2
2 3
8 1
2
10 2
2 5
12 2
2 3
2
500000006
666666674
833333342
666666674
233333338