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;
#define LL long long
#define MOD 1000000007
#define MAXK 100002

int N, K;
LL ans = 0;
LL g[MAXK] = {0};

LL fastPow (LL a, LL k) {
	if (a == 0) return 0;

	LL res = 1;
	LL base = a % MOD;
	while (k) {
		if (k & 1) {
			res = res * base % MOD;
		}
		base = base * base % MOD;
		k >>= 1;
	}
	return res % MOD;
}

int main () {
	cin >> N >> K;

	for (int i = K; i >= 1; i --) {
		g[i] = fastPow (K / i, N);
		for (int j = i * 2; j <= K; j += i) {
			g[i] = (g[i] - g[j] + MOD) % MOD;
		}
		ans = (ans + (g[i] * i) % MOD) % MOD;
	}

	cout << ans;
	return 0;
}