#include using namespace std; #define mod 1000000007 int _I(){int x; scanf("%d",&x); return x;} int prime[1000001]; vector v; void sv(){ int i,j; v.push_back(2); for(i=3; i<=1000000; i+=2){ if(!prime[i]){ v.push_back(i); for(j=i*3; j<=1000000; j+=i+i) prime[j]=1; } } } long long bigmod(long long b,long long p){ if(p==0) return 1; long long r=bigmod(b,p/2); r=(r*r)%mod; if(p&1){ r=(r*b)%mod; } return r; } long long invmod(long long n){ return bigmod(n,mod-2); } int main() { sv(); int n=_I(); for(int i=0; i