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
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Supplier<String> sc) {
		int N = Integer.parseInt(sc.get());
		int K = Integer.parseInt(sc.get());
		var mod = 1000000007;
		long sum = 0;
		var ints = new long[K];
		for (int i = K; i >= 1; i--) {
			int count = 0;
			long minus = 0;
			for (int j = i; j <= K; j+=i) {
				if (j % i != 0) continue;
				count += 1;
				minus = (minus + ints[j - 1]) % mod;
			}
			long pow = (modpow(count, N, mod) - minus) % mod;
			ints[i - 1] = pow = pow < 0 ? pow + mod : pow;
			sum = (sum + ((i * pow) % mod)) % mod;
		}
		System.out.println(sum % mod);
	}

	int gcd(int a, int b) {
	    return b == 0 ? a : gcd(b, a % b);
	}

	long modpow(long a, long n, long mod) {
		long res = 1;
		while (n > 0) {
			if ((n & 1) == 1) res = res * a % mod;
			a = a * a % mod;
			n >>= 1;
		}
		return res;
	}
}

class Main {
	public static void main(String... args) {
		var reader = new BufferedReader(new InputStreamReader(System.in));
		Solver.INSTANCE.solve(new Supplier<>() {
			private StringTokenizer line;

			public String get() {
				try {
					return (line = line != null && line.hasMoreTokens() ? line : new StringTokenizer(reader.readLine())).nextToken();
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
		});
	}
}