Problem: Let's call an array a of size n coprime iff gcd(a1, a2, ..., an) = 1, where gcd is the greatest common divisor of the arguments.

You are given two numbers n and k. For each i (1 ≤ i ≤ k) you have to determine the number of coprime arrays a of size n such that for every j (1 ≤ j ≤ n) 1 ≤ aj ≤ i. Since the answers can be very large, you have to calculate them modulo 109 + 7.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 2·106) — the size of the desired arrays and the maximum upper bound on elements, respectively.

Output

Since printing 2·106 numbers may take a lot of time, you have to output the answer in such a way:

Let bi be the number of coprime arrays with elements in range [1, i], taken modulo 109 + 7. You have to print <image>, taken modulo 109 + 7. Here <image> denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).

Examples

Input

3 4


Output

82


Input

2000000 8


Output

339310063

Note

Explanation of the example:

Since the number of coprime arrays is large, we will list the arrays that are non-coprime, but contain only elements in range [1, i]:

For i = 1, the only array is coprime. b1 = 1.

For i = 2, array [2, 2, 2] is not coprime. b2 = 7.

For i = 3, arrays [2, 2, 2] and [3, 3, 3] are not coprime. b3 = 25.

For i = 4, arrays [2, 2, 2], [3, 3, 3], [2, 2, 4], [2, 4, 2], [2, 4, 4], [4, 2, 2], [4, 2, 4], [4, 4, 2] and [4, 4, 4] are not coprime. b4 = 55.

Solution (in JAVA):

Solution:
/* Author: Ronak Agarwal */
import java.io.* ; import java.util.* ; import java.math.* ;
import static java.lang.Math.min ;
import static java.lang.Math.max ;
import static java.lang.Math.abs ;
import static java.lang.Math.log ;
import static java.lang.Math.pow ;
import static java.lang.Math.sqrt ;
/* Thread is created here to increase the stack size of the java code so that recursive dfs can be performed */
public class Codeshefcode{
	public static void main(String[] args) throws IOException{
		new Thread(null,new Runnable(){	public void run(){ exec_Code() ;} },"Solver",1l<<27).start() ;
	}
	static void exec_Code(){
		try{
			Solver Machine = new Solver() ;
			Machine.Solve() ; Machine.Finish() ;}
		catch(Exception e){ e.printStackTrace() ; print_and_exit() ;}
		catch(Error e){ e.printStackTrace() ; print_and_exit() ; }
	}
	static void print_and_exit(){ System.out.flush() ; System.exit(-1) ;}
}
class Reader{
	BufferedReader reader;
	StringTokenizer tkz;
	Reader(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input)) ;
		tkz = new StringTokenizer("") ;
	}
	String s() throws IOException{
		while (!tkz.hasMoreTokens()) tkz = new StringTokenizer(reader.readLine()) ;
		return tkz.nextToken() ;
	}
	int i() throws IOException{ return Integer.parseInt(s()) ;}
	long l() throws IOException{ return Long.parseLong(s()) ;}
	double d() throws IOException{	return Double.parseDouble(s()) ;}
}
/* All the useful functions,constants,renamings are here*/
class Template{
	/* Constants Section */
	final int INT_MIN = Integer.MIN_VALUE ; final int INT_MAX = Integer.MAX_VALUE ;
	final long LONG_MIN = Long.MIN_VALUE ; final long LONG_MAX = Long.MAX_VALUE ;
	static long MOD = 1000000007 ;
	static Reader ip = new Reader(System.in) ;	
	static PrintWriter op = new PrintWriter(System.out) ;
	/* Methods for writing */
	static void p(Object o){ op.print(o) ; }
	static void pln(Object o){ op.println(o) ;}
	static void Finish(){ op.flush();	op.close(); }
	/* Implementation of operations modulo MOD */
	static long inv(long a){ return powM(a,MOD-2) ; }
	static long m(long a,long b){ return (a*b)%MOD ; }
	static long d(long a,long b){ return (a*inv(b))%MOD ; }
	static long powM(long a,long b){
		if(b<0) return powM(inv(a),-b) ;
		long val=a ; long ans=1 ;
		while(b!=0){
			if((b&1)==1) ans = (ans*val)%MOD ; 
			val = (val*val)%MOD ; 
			b/=2 ;
		}
		return ans ;
	}
	/* Renaming of some generic utility classes */
	final static class mylist extends ArrayList<Integer>{}
	final static class mylisti extends ArrayList<Integer>{}
	final static class myset extends TreeSet<Long>{}
	final static class mystack extends Stack<Integer>{}
	final static class mymap extends TreeMap<Long,Integer>{}
}
/* Implementation of the pair class, useful for every other problem */
class pair implements Comparable<pair>{
	int x ; int y ; int id ;
	pair(int _x,int _y,int _id){ x=_x ; y=_y ; id=_id ;} 
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}
/* Main code starts here */
class Solver extends Template{
	int n,k ;
	int LIM = 2000000 ;
	long pn[] = new long[LIM+1] ;
	long u[] = new long[LIM+1] ;
	int fac[] = new int[LIM+1] ;
	void preComp(){
		for(int i=1 ; i<=LIM ; i++) pn[i] = powM(i,n) ;
		for(int i=2 ; i<=LIM ; i++) 
			if(fac[i]==0)
				for(int j=i ; j<=LIM ; j+=i)
					fac[j] = i ;
		u[1] = 1 ;
		for(int i=2 ; i<=LIM ; i++){
			int prm = fac[i] ;
			int j = i/prm ;
			u[i] = (j%prm==0 ? 0 : -u[j]) ;
		}
		for(int i=1 ; i<=LIM ; i++) u[i] = (u[i]+MOD)%MOD ; 
	}
	long res[] ;
	public void Solve() throws IOException{
		n = ip.i() ; k = ip.i() ;
		preComp() ;
		res = new long[k+1] ;
		long vl = 0 ;
		for(int j=1 ; j<=k ; j++)
			for(int i=j ; i<=k ; i+=j){
				long diff = pn[i/j]-pn[(i-1)/j] ;
				if(diff<0) diff+=MOD ;
				res[i] = (res[i]+m(u[j],diff))%MOD ;
			}
		for(int i=1 ; i<=k ; i++) res[i] = (res[i]+res[i-1])%MOD ;
		long ans=0 ;
		for(long i=1 ; i<=k ; i++)
			ans+=(res[(int) i]^i) ;
		pln(ans%MOD) ;
	}
}