有n个格子,每个格子里有一个数,1234...n
牛牛放出无穷只青蛙.
用数学语言描述,第i只青蛙的路线是首项为1,公比为$p(i)$的等比数列,其中$p(i)$代表第i个素数.
当青蛙跳到一个格子上,如果这个格子上面有一个数,青蛙就会把这个数吃掉.
牛牛想知道,所有没有被吃掉的数的lcm是多少?
由于这个lcm可能非常大,请输出它对$10^9+7$取模的值.
我们需要求所有没有被吃掉的数的lcm.
对于没有被吃掉的数来说,他们的lcm必然是所有数的因子的最大指数相乘.
那么由题目知道,被吃掉的数是小于n的质因子的次方.
如果某个数不被吃掉,那么他至少是两个质因子的乘积.
那么我们只需要求对于某个质因子来说,n以内的最大的次方,最后把乘积输出即可.
对于2来说,他本身就是最小的,所以最大的数是$3*2^k$,k就是最大的次方.
对于其他的质数来说,最大的数就是$2*p^k$.
因为不被吃掉的数至少是两个质因数相乘,所以质数筛只要筛到$\frac{n}{2}$就行,不然会超时.