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.*;
import java.io.*;
 
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        
        int BIG_NUMBER = 100000000;
        long LARGE_NUMBER = 10000000000000000L;
        
        int l=sc.nextInt();
        int k=sc.nextInt();
        
        long[] dp = new long[k+1];    //gcd=kとなる組み合わせの個数
        
        long ans=0;
    	for(int i=k; i>0; i--){
    	    int toubai = k/i;
    	    dp[i] = pow10E97(toubai,l);
    		for(int j=2; j<=toubai; j++){
    		    dp[i] -= dp[i*j];
    		}
    		ans += divBy10E97(dp[i]*i);
   		}
        ans = divBy10E97(ans);
        out.println(ans);
        out.flush();
    }
    
    private static long e97 = (long)1e9 + 7;
    
    private static long pow10E97(long ob, int soeji){
        if(soeji==2) return divBy10E97(ob*ob);
        
        int d = getDigit2L(soeji);
        long[] ob_pow_2pow = new long[d];
        
        ob_pow_2pow[0] = ob;
	   	for(int i=1; i<d; i++){
	   	    ob_pow_2pow[i] = divBy10E97(ob_pow_2pow[i-1]*ob_pow_2pow[i-1]);
	   	}
	   	
	   	long ans=1;
    	for(int i=d-1; i>=0; i--){
    	    if(soeji >= (1<<i)){
    	        soeji -= (1<<i);
    	        ans = divBy10E97(ans*ob_pow_2pow[i]);
    	    }
   		}
	   	
        return ans;
    }
    
    private static long divBy10E97(long in){
        return in%e97;
    }
    
    private static int getDigit2L(long num){
        long cf = 1;
        int d=0;
        while(num >= cf){
            d++;
            cf = 1<<d;
        }
        return d;   //numはd桁の数で、2^dより小さい
    }
    
    private static int getDigit10L(long num){
        long cf = 1;
        int d=0;
        while(num >= cf){
            d++;
            cf*=10;
        }
        return d; //numはd桁の数で、10^dより小さい
    }
    
    private static void fillL(long[] ob, long res){
	   	for(int i=0; i<ob.length; i++){
	   	    ob[i] = res;
	   	}
	   	return;
    }
    private static void fill2L(long[][] ob, long res){
	   	for(int i=0; i<ob.length; i++){
    		for(int j=0; j<ob[0].length; j++){
	   	        ob[i][j] = res;
    		}
	   	}
	   	return;
    }
    private static void fill2(int[][] ob, int res){
	   	for(int i=0; i<ob.length; i++){
    		for(int j=0; j<ob[0].length; j++){
	   	        ob[i][j] = res;
    		}
	   	}
	   	return;
    }
    private static void fill(int[] ob, int res){
	   	for(int i=0; i<ob.length; i++){
	   	    ob[i] = res;
	   	}
	   	return;
    }
    
    private static long gcd(long m, long n) {
        if(m < n) return gcd(n, m);
        if(n == 0) return m;
        return gcd(n, m % n);
    }
    
    private static int pow2(int in){
        return in*in;
    }
    private static long pow2L(long in){
        return in*in;
    }
    
    private static int minExcept(int[] dt, int ex, char mode){
        int min=Integer.MAX_VALUE;
        
        if(mode =='a'){
        	for(int i=0; i<dt.length; i++){
        	    if((i != ex) && (dt[i] < min)) min = dt[i];
        	}
        }else if(mode =='v'){
        	for(int i=0; i<dt.length; i++){
        	    if((dt[i] != ex) && (dt[i] < min)) min = dt[i];
        	}
        }
    	return min;
    }
    private static long minExcept(long[] dt, int ex, char mode){
        long min=Long.MAX_VALUE;
        
        if(mode =='a'){
        	for(int i=0; i<dt.length; i++){
        	    if((i != ex) && (dt[i] < min)) min = dt[i];
        	}
        }else if(mode =='v'){
        	for(int i=0; i<dt.length; i++){
        	    if((dt[i] != ex) && (dt[i] < min)) min = dt[i];
        	}
        }
    	return min;
    }
    
    private static int abs(int a){
        if(a>=0) return a;
        else return -a;
    }
    private static long absL(long a){
        if(a>=0) return a;
        else return -a;
    }
    private static int min(int a, int b){
        if(a>b) return b;
        else return a;
    }
    private static long minL(long a, long b){
        if(a>b) return b;
        else return a;
    }
    private static int min2(int... ins){
        int min = ins[0];
        
    	for(int i=1; i<ins.length; i++){
    	    if(ins[i] < min) min = ins[i];
    	}
    	return min;
    }
    private static int max(int a, int b){
        if(a>b) return a;
        else return b;
    }
    private static long maxL(long a, long b){
        if(a>b) return a;
        else return b;
    }
    private static int max2(int... ins){
        int max = ins[0];
        
    	for(int i=1; i<ins.length; i++){
    	    if(ins[i] > max) max = ins[i];
    	}
    	return max;
    }
    
    
    static void show_i2d_array(long[][] dt){
        PrintWriter out = new PrintWriter(System.out);
    	for(int i=0; i<dt[0].length; i++){
    		for(int j=0; j<dt.length; j++){
    		    out.print(dt[j][i]+",");
    		}
    		out.println("<-city="+i);
    	}
    	out.flush();
    }
    
    public static void combSort(int[][] origin, int ln){
        int h=ln*10/13, tmp=0;
        boolean fin=true;
        while((h>1)||(!fin)){
            fin=true;
            for(int i=0; i < ln-h; i++){
                if(origin[i][0] > origin[i+h][0]){
                    tmp=origin[i][0];
                    origin[i][0]=origin[i+h][0];
                    origin[i+h][0]=tmp;
                    tmp=origin[i][1];
                    origin[i][1]=origin[i+h][1];
                    origin[i+h][1]=tmp;
                    fin=false;
                }
            }
            h *=10;
            h/=13;
        }
    }
}
 
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}