#4961. 除除除

内存限制:128 MiB 时间限制:10 Sec

题目描述

我们定义一种操作是将一个正整数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即可。

输入格式

输入包含多组测试数据,以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组数据。

输出格式

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

样例

样例输入


			
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

数据范围与提示