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
// practice with kaiboy
import java.io.*;
import java.util.*;

public class Main extends PrintWriter {
	Main() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		Main o = new Main(); o.main(); o.flush();
	}

	static final int MD = 1000000007;
	int power(long a, int k) {
		long p = 1;
		while (k > 0) {
			if ((k & 1) == 1)
				p = p * a % MD;
			a = a * a % MD;
			k >>= 1;
		}
		return (int) p;
	}
	void main() {
		int m = sc.nextInt();
		int n = sc.nextInt();
		byte[] mobius = new byte[n + 1]; Arrays.fill(mobius, (byte) 2);
		mobius[1] = 1;
		for (int a = 2; a <= n; a++) {
			if (mobius[a] != 2)
				continue;
			for (int b = a; b <= n; b += a)
				if (mobius[b] == 2)
					mobius[b] = -1;
				else
					mobius[b] *= -1;
			if (a <= n / a) {
				int a2 = a * a;
				for (int b = a2; b <= n; b += a2)
					mobius[b] = 0;
			}
		}
		int[] kk = new int[n + 1];
		for (int a = 1, b = n; a <= n / a; a++) {
			kk[a] = power(n / a, m);
			int p = power(a, m);
			while (b > n / (a + 1))
				kk[b--] = p;
		}
		long ans = 0;
		for (int a = 1; a <= n; a++) {
			int k = 0;
			for (int b = 1; b <= n / a; b++)
				k = (k + kk[a * b] * mobius[b]) % MD;
			ans = (ans + (long) k * a) % MD;
		}
		if (ans < 0)
			ans += MD;
		println(ans);
	}
}
