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
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static long MOD = 1000000007L;
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      long n = Long.parseLong(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      
      
      long answer = 0L;
      long[] sums = new long[(int)m+1];
      
      for(int k = m; k >= 1; k--){
         /*long num = ((exp(m/k,n)-sums[(int)k]+MOD)%MOD+MOD)%MOD;
         
         
         for(int j = 1; j*j <= k; j++){
            if(k%j == 0) sums[j] = (sums[j] + num + MOD)%MOD;
         }*/
         
         long num = exp((long)(m/k),n);
         
         for(int j = k*2; j <= m; j += k){
            num = num-sums[j];
            if(num < 0) num += MOD;
         }
         
         sums[k] = num;
         
         
         answer = (answer + k*num + MOD)%MOD;
      }
      
      
      out.println(answer);
      
      
      out.close();
   }
   
   public static long exp(long base, long power){
      if(power == 0) 
         return 1;
      if(power == 1) 
         return (base + MOD) % MOD;
      long ans = exp(base,power/2);
      ans = (ans*ans + MOD) % MOD;
      if(power%2 == 1) ans = (ans*base + MOD) % MOD;
      return (ans + MOD) % MOD;
   }
   
      
}