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:


import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;

/**
 * Created by dalt on 2018/3/20.
 */
public class CF915G {
    public static final long MODULO = 1000000007;
    static final boolean IS_OJ = System.getProperty("ONLINE_JUDGE") != null;
    public static BlockReader input;

    public static void main(String[] args) throws FileNotFoundException {
        if (!IS_OJ) {
            System.setIn(new FileInputStream("D:\\DataBase\\TESTCASE\\codeforces\\CF915G.in"));
        }
        input = new BlockReader(System.in);

        int n = input.nextInteger();
        int k = input.nextInteger();
        int[]  mobius = new int[k + 1];
        int[] primes = new int[k + 1];
        int primeCnt = 0;
        long[]  pns = new long[k + 1];
        boolean[] isComposites = new boolean[k + 1];

        //euler griddle
        mobius[1] = 1;
        pns[1] = 1;
        isComposites[1] = true;
        for (int i = 2; i <= k; i++) {
            if (!isComposites[i]) {
                primes[primeCnt++] = i;
                pns[i] = pow(i, n);
                mobius[i] = -1;
            }
            //i * primes[j] <= k => primes[j] <= k / i
            for (int j = 0, bound = k / i; j < primeCnt && primes[j] <= bound; j++) {
                int ip = i * primes[j];
                isComposites[ip] = true;
                pns[ip] = pns[i] * pns[primes[j]] % MODULO;
                if (i % primes[j] == 0) {
                    mobius[ip] = 0;
                    break;
                }
                mobius[ip] = mobius[i] * mobius[primes[j]];
            }
        }


        long[] differ = new long[k + 1];
        for (int i = 1; i <= k; i++) {
            for (int j = i, t = 1; j <= k; j += i, t++) {
                differ[j] += (pns[t] - pns[t - 1]) * mobius[i];
            }
        }


        long[] values = new long[k + 1];
        values[1] = 1;
        for (int i = 2; i <= k; i++) {
            values[i] = ((values[i - 1] + differ[i]) % MODULO + MODULO) % MODULO;
        }

        long sum = 0;
        for (int i = 1; i <= k; i++) {
            sum += values[i] ^ (long)i;
        }

        sum = (sum % MODULO + MODULO) % MODULO;
        System.out.println(sum);
    }

    public static long pow(long x, int n) {
        int bit = 31;
        while (bit >= 0 && (n & (1 << bit)) == 0) {
            bit--;
        }

        long v = 1;
        for (; bit >= 0; bit--) {
            v = v * v % MODULO;
            if ((n & (1 << bit)) != 0) {
                v = v * x % MODULO;
            }
        }

        return v;
    }

    public static class BlockReader {
        static final int EOF = -1;
        InputStream is;
        byte[] dBuf;
        int dPos, dSize, next;
        StringBuilder builder = new StringBuilder();

        public BlockReader(InputStream is) {
            this(is, 4096);
        }

        public BlockReader(InputStream is, int bufSize) {
            this.is = is;
            dBuf = new byte[bufSize];
            next = nextByte();
        }

        public int nextByte() {
            while (dPos >= dSize) {
                if (dSize == -1) {
                    return EOF;
                }
                dPos = 0;
                try {
                    dSize = is.read(dBuf);
                } catch (Exception e) {
                }
            }
            return dBuf[dPos++];
        }

        public String nextBlock() {
            builder.setLength(0);
            skipBlank();
            while (next != EOF && !Character.isWhitespace(next)) {
                builder.append((char) next);
                next = nextByte();
            }
            return builder.toString();
        }

        public void skipBlank() {
            while (Character.isWhitespace(next)) {
                next = nextByte();
            }
        }

        public int nextInteger() {
            skipBlank();
            int ret = 0;
            boolean rev = false;
            if (next == '+' || next == '-') {
                rev = next == '-';
                next = nextByte();
            }
            while (next >= '0' && next <= '9') {
                ret = (ret << 3) + (ret << 1) + next - '0';
                next = nextByte();
            }
            return rev ? -ret : ret;
        }

        public int nextBlock(char[] data, int offset) {
            skipBlank();
            int index = offset;
            int bound = data.length;
            while (next != EOF && index < bound && !Character.isWhitespace(next)) {
                data[index++] = (char) next;
                next = nextByte();
            }
            return index - offset;
        }

        public boolean hasMore() {
            skipBlank();
            return next != EOF;
        }
    }
}