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.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		final int mod = (int)Math.pow(10, 9) + 7;
		
		int n = scan.nextInt();
		int k = scan.nextInt();
		
		long[] gdc = new long[k+1]; //gdc[i]は最大公約数がiである数列の個数
		for(int i = k; i > 0; i--) {
			gdc[i] = pow(k/i, n, mod);
			for(int j = 2; (long)i*j < k+1 ;j++)
				gdc[i] = (gdc[i] - gdc[i*j] + mod) % mod;
		}
		
		long ans = 0;
		for(int i = 1; i < k+1; i++) {
			ans += (long)i*gdc[i];
			ans %= mod;
		}
		
		System.out.println((ans+mod)%mod);
	}
	
	static long pow(long a, long n,final int mod) {
		long ans = 1;
		while(n > 0) {
			if((n&1) == 1) ans = ans * a % mod;
			a = a*a%mod;
			n >>= 1;
		}
		return ans;
	}
}
