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>
#define LL long long
using namespace std;
const int maxn=100005,K=1000000007;
int n,m,ans,f[maxn];
int Pow(int A,int B)
{
	int res=1;
	while (B)
	{
		if (B&1) res=(LL)res*A%K;
		A=(LL)A*A%K;
		B>>=1;
	}
	return res;
}
int finds(int k)
{
	if (f[k]) return f[k];
	int res=Pow(k,n);
	for (int i=2;i<=k;i++)
	{
		res-=finds(k/i);
		if (res<0) res+=K;
	}
	return f[k]=res;
}
int main()
{
	scanf("%d%d",&n,&m);
	f[1]=1;
	ans=finds(m);
	for (int i=2;i<=m;i++) ans=(ans+(LL)f[m/i]*i)%K;
	printf("%d\n",ans);
	return 0;
}
