Consider sequences \\{A_1,...,A_N\\} of length N consisting of integers between 1 and K (inclusive).

There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.

Since this sum can be enormous, print the value modulo (10^9+7).

Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq K \leq 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K


Output

Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

Examples

Input

3 2


Output

9


Input

3 200


Output

10813692


Input

100000 100000


Output

742202979
#include<iostream>
using namespace std;
long pow(long x, long n, long m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return pow(x * x % m, n / 2, m);
  else
    return x * pow(x, n - 1, m) % m;
}

int main(){
  long n,k;
  cin>>n>>k;
  long ans,mod;
  ans=0;
  mod=1000000007;
  long a[k+1];
  for(long l=k; l>0; l--){
    long x=pow(k/l,n,mod);
    for (long d=2;d<k/l+1;d++){
      x-=a[d*l];
      x%=mod;
    }
    
    a[l]=x;

  }
  for (long i=1; i<k+1; i++){
    ans+=a[i]*i;
    ans%=mod;
  }

  cout<<ans%mod<<endl;
  
  return 0;
}

