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