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.*;

public class Main {

  static final long MOD = 1000000007;
  static long n, k, ans;

  static long fastPowMOD(long base, long expo){
    long ret = 1;
    base %= MOD;
    while(expo > 0){
      if(expo % 2 == 1){
        ret *= base;
      }
      expo >>= 1;
      base *= base;
      base %= MOD;
      ret %= MOD;
    }
    return ret;
}

  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    String[] in = br.readLine().split(" ");
    n = Long.parseLong(in[0]);
    k = Long.parseLong(in[1]);

    br.close();

    ans = fastPowMOD(k, n);
    long[] occupied = new long[(int)(k + 1)];

    for(long i = k; i >= 2; i--){
      long num = k / i;
      long pat = (fastPowMOD(num, n) - occupied[(int)i]) % MOD;
      if(pat < 0) pat += MOD;
      ans += (pat * (i - 1)) % MOD;
      ans %= MOD;

      long tmp = i;
      for(long j = 2; j * j <= tmp; j++){
        if(tmp % j == 0){
          occupied[(int)j] += pat;
          occupied[(int)j] %= MOD;
          if(tmp / j != j){
            occupied[(int)(tmp / j)] += pat;
            occupied[(int)(tmp / j)] %= MOD;
          }
        }
      }
    }

    System.out.println(ans);

  }
}