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.lang.*;
import java.util.*;
public class Main{
    public static long pow(long a,long b,long m){
        if(a==0 || a==1) return a;
        if(b==1) return a%m;
        long c=pow(a,b/2,m);
        if(b%2==0) return (c*c)%m;
        else return (((c*c)%m*(a%m))%m);
    }
    public static long sumGCD(long[] arr ,long n,long m){
        long max=0;
        for(int i=0;i<arr.length;i++)
            if(arr[i]>max) max=arr[i];
        long[] c=new long[(int)max+1];
        long[] d=new long[(int)max+1];
        long[] e=new long[(int)max+1];
        for(int i=0;i<arr.length;i++) c[(int)arr[i]]++;
        for(int i=1;i<=max;i++){
            for(int j=i;j<=max;j+=i) d[i]+=c[j];
        }
        for(int i=(int)max;i>=1;i--){
            e[i] = pow(d[i],n,m);
            for(int j=2*i;j<=max;j+=i){
                e[i] -= e[j];
                if(e[i]<=0) e[i]+=m;
            }
        }
        long sum=0;
        for(int i=1;i<=max;i++) sum=(sum+i*e[i])%m;
        return sum;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] str=br.readLine().split(" ");
        long n=Long.parseLong(str[0]);
        long k=Long.parseLong(str[1]);
        long[] arr=new long[(int)k];
        for(int i=1;i<=k;i++) arr[i-1]=i;
        long ans=sumGCD(arr,n,1000000007);
        System.out.println(ans);
    }
}