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