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;

const int km = 1e5, mod = 1e9 + 7;
long long s[km + 1];
int n, k;
long long ans = 0;
int pow(int x, int y) { //x^y
	int rv = 1;
	for (; y > 0; y >>= 1, x = (long long) x * x % mod)
		if (y & 1)
			rv = (long long) rv * x % mod;
	return rv;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		ans += (long long) pow(k / i, n) * (i - s[i]) % mod;
		for (int j = i * 2; j <= k; j += i) {
			s[j] += i - s[i];
		}
	}
	ans %= mod;
	if (ans < 0)
		ans += mod;
	cout << ans << endl;

}
