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>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 100005, P = 1e9 + 7;

int n, K, f[N];

int inline power(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = (LL)res * a % P;
		a = (LL)a * a % P;
		b >>= 1;
	}
	return res;
}

int main() {
	scanf("%d%d", &n, &K);
	for (int i = K; i; i--) {
		int t = K / i;
		f[i] = power(t, n);
		for (int j = i * 2; j <= K; j += i) f[i] = ((LL)f[i] - f[j] + P) % P;
	}
	LL ans = 0;
	for (int i = 1; i <= K; i++) {
		int t = K / i;
		ans = (ans + (LL)i * f[i]) % P;
	}
	printf("%lld\n", ans);
	return 0;
}