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 <cstdio>
#define ll long long
ll mod = 1000000007;
ll big(ll b, ll p){
	if (p == 1) return b;
	ll h = big(b, p / 2);
	ll res = (h * h) % mod;
	if (p % 2 == 1) res = (res * b) % mod;
	return res;
}
int main(){
	ll n, k;
	scanf("%lld %lld", &n, &k);
	ll a[k + 1], ans = 0;
	for (int i = k; i >= 1; i--){
		a[i] = big(k / i, n);
		for (int j = 2; i * j <= k; j++){
			(a[i] += mod - a[i * j]) %= mod;
		}
	}
	for (int i = 1; i <= k; i++){
		(ans += (i * a[i]) % mod) %= mod;
	}
	printf("%lld\n", ans);
}