Discipntion

Let's call an array a of size n coprime iff gcd(a₁, a₂, ..., a_n) = 1, where gcd is the greatest common divisor of the arguments.

You are given two numbers n and k. For each i (1 ≤ i ≤ k) you have to determine the number of coprime arrays a of size n such that for every j (1 ≤ j ≤ n) 1 ≤ a_j ≤ i. Since the answers can be very large, you have to calculate them modulo 10⁹ + 7.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 2·10⁶) — the size of the desired arrays and the maximum upper bound on elements, respectively.

Output

Since printing 2·10⁶ numbers may take a lot of time, you have to output the answer in such a way:

Let b_i be the number of coprime arrays with elements in range [1, i], taken modulo 10⁹ + 7. You have to print , taken modulo 10⁹ + 7. Here  denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).

Example

Input

3 4

Output

82

Input

2000000 8

Output

339310063

Note

Explanation of the example:

Since the number of coprime arrays is large, we will list the arrays that are non-coprime, but contain only elements in range [1, i]:

For i = 1, the only array is coprime. b₁ = 1.

For i = 2, array [2, 2, 2] is not coprime. b₂ = 7.

For i = 3, arrays [2, 2, 2] and [3, 3, 3] are not coprime. b₃ = 25.

For i = 4, arrays [2, 2, 2], [3, 3, 3], [2, 2, 4], [2, 4, 2], [2, 4, 4], [4, 2, 2], [4, 2, 4], [4, 4, 2] and [4, 4, 4] are not coprime. b₄ = 55.

 

 

一开始没有想到题目求b的整体性，，，直接用了一个简单的容斥，，，然后就T了。。

如下

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long long #define ha 1000000007#define maxn 2000005using namespace std;int ans[maxn],n,k,tot;inline int ksm(int x,int y){ int an=1; for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha; return an;}inline void get(int x){ ans[x]=-ksm(x,n); for(int i=2,j,now;i<=x;i=j+1){ now=x/i,j=x/now; ans[x]=((ll)ans[x]+(ll)(j-i+1)*(ll)ans[now])%ha; } ans[x]=-ans[x]; if(ans[x]<0) ans[x]+=ha;}int main(){ scanf("%d%d",&n,&k); ans[1]=1; for(int i=2;i<=k;i++) get(i); tot=0; for(int i=1;i<=k;i++){ tot+=ans[i]^i; while(tot>=ha) tot-=ha; } printf("%d\n",tot); return 0;}
            
           
          
         
        
       

　　

 

 

后来发现还是要上反演才能过啊hhhh。

当我们求b[t]的时候：

设g(x)为gcd是x的倍数的数组个数，

显然g(x)=(t/x)^n;

设f(x)为gcd==x的数组个数，

显然g(x)=Σf(x*i)

所以=> f(x)=Σg(x*i)*μ(i)

我们求的显然是f(1),

所以b[t]=Σg(i)*μ(i)=Σ μ(i) * (t/i)^n

 

我们考虑通过b[t-1]推b[t]，发现只有i是t的约数时(t/i)变化了，且都是+1；而对于其他的i，(t/i)不变。

所以我们可以先预处理出b[]的差分(可以做到调和级数的N ln N，通过枚举i，但前提是你得先预处理出(1-k)的n次方最好再把次方的差分也一起算出来)。

最后求差分的前缀和就是b[]了。

正解如下

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long long #define ha 1000000007#define maxn 2000005using namespace std;int ans[maxn],n,k,tot;int ci[maxn],u[maxn];int zs[1000000],t=0;bool v[maxn];inline void init(){ u[1]=1; for(int i=2;i<=2000000;i++){ if(!v[i]) zs[++t]=i,u[i]=-1; for(int j=1,w;j<=t&&(w=zs[j]*i)<=2000000;j++){ v[w]=1; if(!(i%zs[j])) break; u[w]=-u[i]; } }}inline int ksm(int x,int y){ int an=1; for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha; return an;}int main(){ init(); scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) ci[i]=ksm(i,n); for(int i=k;i;i--){ ci[i]-=ci[i-1]; if(ci[i]<0) ci[i]+=ha; } for(int i=1;i<=k;i++) for(int j=i;j<=k;j+=i){ ans[j]+=u[i]*ci[j/i]; if(ans[j]<0) ans[j]+=ha; else if(ans[j]>=ha) ans[j]-=ha; } for(int i=1;i<=k;i++){ ans[i]+=ans[i-1]; if(ans[i]>=ha) ans[i]-=ha; tot+=ans[i]^i; while(tot>=ha) tot-=ha; } printf("%d\n",tot); return 0;}