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<bits/stdc++.h>
using namespace std;

int n,k;
long long s,s1,m=1e9+7,b[100001];

int xar(int n, int p){
    long long s;
    if ( p==1 )
        return n;

    long long l=xar(n, p/2);

    if (p%2==1)
      s=(((l*l)%m)*n)%m;
    else
      s=(l*l)%m;

    return s%m;
}

int main()
{
	ios::sync_with_stdio(0);
	
	cin >> n >> k;
	
	for (int i=k; i>=1; i--){
		int j=i+i;
		
		while(j<=k){
			s+=b[j];
			s%=m;
			j+=i;
		}
		
		b[i]=((xar(k/i, n) % m)-s)%m;
		b[i]=(b[i]+m)%m;
		s=0;
		s1=0;
	}
	
	for (int i=1; i<=k; i++){
		s+=(b[i]*i)%m;
		//cout << b[i] << " ";
		s%=m;
		s=(s+m)%m;
	}
	cout << s << endl;
}
