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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const long double eps = 1e-6;
const long double pi = acos(-1.0);
long double sign(long double x) { return (x > 0) - (x < 0); }
long long sign(long long x) { return (x > 0) - (x < 0); }
int sign(int x) { return (x > 0) - (x < 0); }
struct pt {
  long double x, y;
  pt() {}
  pt(long double _x, long double _y) : x(_x), y(_y) {}
  bool operator<(pt p) { return tie(x, y) < tie(p.x, p.y); }
  bool operator==(pt p) { return tie(x, y) == tie(p.x, p.y); }
  pt operator+(pt p) { return {x + p.x, y + p.y}; }
  pt operator-(pt p) { return {x - p.x, y - p.y}; }
  pt operator*(long double d) { return {x * d, y * d}; }
  pt operator/(long double d) { return {x / d, y / d}; }
  long double dot(pt p) { return x * p.x + y * p.y; }
  long double det(pt p) { return x * p.y - y * p.x; }
  long double cross(pt p, pt q) { return (p - *this).det(q - *this); }
  long double dist() { return sqrtl(x * x + y * y); }
  pt rot90() { return pt(-y, x); }
  pt unit() { return *this / dist(); }
  long double angle() { return atan2(y, x); }
  pt rot(long double an) {
    return {x * cos(an) - y * sin(an), x * sin(an) + y * cos(an)};
  }
  void read() { cin >> x >> y; }
  void write() { cout << "(" << x << "," << y << ")" << endl; }
};
struct seg {
  pt fi, sc;
  seg() {}
  seg(pt _fi, pt _sc) : fi(_fi), sc(_sc) {}
  long double dist(pt C) {
    if (fi == sc) return (C - fi).dist();
    long double d = pow((sc - fi).dist(), 2);
    long double t = min(d, max((long double)0.0, (C - fi).dot(sc - fi)));
    return ((C - fi) * d - (sc - fi) * t).dist() / d;
  }
  long double len() { return (fi - sc).dist(); }
  bool on_seg(pt C) {
    return abs(C.cross(fi, sc)) < eps && (fi - C).dot(sc - C) <= eps;
  }
  vector<pt> intersect(seg rhs) {
    long double oa = rhs.fi.cross(rhs.sc, fi);
    long double ob = rhs.fi.cross(rhs.sc, sc);
    long double oc = fi.cross(sc, rhs.fi);
    long double od = fi.cross(sc, rhs.sc);
    if (sign(oa) * sign(ob) < 0 && sign(oc) * sign(od) < 0)
      return {(fi * ob - sc * oa) / (ob - oa)};
    vector<pt> ans;
    if (rhs.on_seg(fi)) ans.push_back(fi);
    if (rhs.on_seg(sc)) ans.push_back(sc);
    if (on_seg(rhs.fi)) ans.push_back(rhs.fi);
    if (on_seg(rhs.sc)) ans.push_back(rhs.sc);
    return ans;
  }
};
struct line {
  long double a, b, c;
  line(pt p1, pt p2) {
    assert(!(p1 == p2));
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = a * p1.x + b * p1.y;
  }
  line() {}
  line(long double _a, long double _b, long double _c) : a(_a), b(_b), c(_c) {}
  long double dist(pt p) {
    return fabs(a * p.x + b * p.y - c) / sqrtl(a * a + b * b);
  }
  pair<int, pt> intersect(line rhs) {
    long double dett = a * rhs.b - b * rhs.a;
    if (fabs(dett) <= eps) {
      long double det2 = c * rhs.a - a * rhs.c;
      if (fabs(det2) <= eps) return {-1, pt()};
      return {0, pt()};
    }
    return {1,
            pt((c * rhs.b - rhs.c * b) / dett, (a * rhs.c - c * rhs.a) / dett)};
  }
};
pt reflect(pt A, line L) {
  line perpendicular(-L.b, L.a, -L.b * A.x + L.a * A.y);
  pt insect = perpendicular.intersect(L).second;
  return insect * (long double)2.0 - A;
}
struct mint {
  int val;
  mint() { val = 0; }
  mint(const long long& v) {
    val = (-mod <= v && v < mod) ? v : v % mod;
    if (val < 0) val += mod;
  }
  friend ostream& operator<<(ostream& os, const mint& a) { return os << a.val; }
  friend bool operator==(const mint& a, const mint& b) {
    return a.val == b.val;
  }
  friend bool operator!=(const mint& a, const mint& b) {
    return a.val != b.val;
  }
  friend bool operator<(const mint& a, const mint& b) { return a.val < b.val; }
  friend bool operator>(const mint& a, const mint& b) { return a.val > b.val; }
  friend bool operator<=(const mint& a, const mint& b) {
    return a.val <= b.val;
  }
  friend bool operator>=(const mint& a, const mint& b) {
    return a.val >= b.val;
  }
  mint operator-() { return mint(-val); }
  mint& operator+=(const mint& m) {
    if ((val += m.val) >= mod) val -= mod;
    return *this;
  }
  mint& operator-=(const mint& m) {
    if ((val -= m.val) < 0) val += mod;
    return *this;
  }
  mint& operator*=(const mint& m) {
    val = (val * 1ll * m.val) % mod;
    return *this;
  }
  friend mint pow(mint a, long long p) {
    mint ans = 1;
    for (; p; p /= 2, a *= a)
      if (p % 2 == 1) ans *= a;
    return ans;
  }
  friend mint inv(const mint& a) { return pow(a, mod - 2); }
  mint& operator/=(const mint& m) { return (*this) *= inv(m); }
  mint& operator^=(const mint& m) {
    if ((val ^= m.val) >= mod) val -= mod;
    return *this;
  }
  friend mint operator+(mint a, const mint& b) { return a += b; }
  friend mint operator-(mint a, const mint& b) { return a -= b; }
  friend mint operator*(mint a, const mint& b) { return a *= b; }
  friend mint operator/(mint a, const mint& b) { return a /= b; }
  friend mint operator^(mint a, const mint& b) { return a ^= b; }
};
int solve();
void precomp();
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t = 1;
  if (0) cin >> t;
  if (0) cout << fixed << setprecision(10);
  precomp();
  for (int tc = 1; tc <= t; tc++) {
    if (0 && 0) cout << "Case #" << tc << ": ";
    solve();
  }
}
void precomp() { return; }
int n, k;
mint ans = 0, sum = 0, dp[2000005], pw[2000005];
int solve() {
  cin >> n >> k;
  for (int i = 1; i <= k; i++) pw[i] = pow(mint(i), n);
  for (int i = 1; i <= k; i++) {
    dp[i] += pw[i];
    dp[i] -= pw[i - 1];
    sum += dp[i];
    ans += sum ^ i;
    for (int j = i * 2; j <= k; j += i) dp[j] -= dp[i];
  }
  cout << ans << endl;
  return 0;
}