题意简述：
求出长度为(n)的满足(a_1=2,max(sqrt[i]{a_i})<min(sqrt[i]{a_i+1}))的正整数序列({a})的个数。
答案对(1000000007)取模。
数据范围：
(nle10^{10})
解法：
固定(x=max(sqrt[i]{a_i}))，那么(a_i)需要满足(sqrt[i]{a_i}le x<sqrt[i]{a_i+1})即(a_iin(x^i-1,x^i])，显然合法的取值有且仅有一种。
那么现在我们将问题转化为了求(max(sqrt[i]{a_i}))的取值数。
设(f_i)表示第(i)个位置贡献的方案数，那么答案就是(sumlimits_{i=1}^nf_i)。
根据(a_1)的限制，我们知道(a_iin[2^i,3^i))。
但是显然(f_ile3^i-2^i)，因为某些(sqrt[i]{a_i})会在(sqrt[j]{a_j}(j<i))处被计算，我们钦定相等的值的贡献在最小的(i)处计算。
注意到(sqrt[i]{a_i}=sqrt[j]{a_j}Leftrightarrow a_i=a_j^{(frac ij)})，因为(a_i,a_jinmathbb N)，所以(j|i)。
那么记(g_n=3^n-2^n)，可以得到(f*I=g)，杜教筛即可。