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 p=1e9+7,c,i,mx,k,k1,a[100001];
int ax(int n)
{
	if(n==1)
	return c;
	long long l=ax(n/2);
	if(n%2==0)
	return (l*l)%p;
	
	return ((l*l)%p*c)%p;
}
int main(){
	int n;
	ios::sync_with_stdio(0);
	cin>>n>>k;
	k1=k;
	for(k1=k;k1>0;k1--)
	{
		if(k/k1==1)
		{
			a[k1]=1;
			continue;
		}
		c=k/k1;
		a[k1]=ax(n);
		for(i=2;i<=c;i++)
		{
			a[k1]-=a[i*k1];
			a[k1]%=p;
			a[k1]+=p;
			a[k1]%=p;
		}
	}
	for(i=1;i<=k;i++)
	{
		mx+=((long long)a[i]*i)%p;
		mx%=p;
	}
	cout<<mx;
}
