#include <bits/stdc++.h>
inline int qpow(int x, int y, int mod, int ret = 1) {
  for (; y; y >>= 1, x = 1ll * x * x % mod)
    if (y & 1) ret = 1ll * ret * x % mod;
  return ret;
}
const int mod = 1e9 + 7;
const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
const long long mod_1_2 = 1ll * mod1 * mod2;
const int inv_1 = qpow(mod1, mod2 - 2, mod2),
          inv_2 = qpow(mod_1_2 % mod3, mod3 - 2, mod3);
struct crt {
  int a, b, c;
  crt() {}
  crt(int _a) { a = b = c = _a; }
  crt(int _a, int _b, int _c) { a = _a, b = _b, c = _c; }
  inline friend crt upd(const crt &p) {
    return crt(p.a + (p.a >> 31 & mod1), p.b + (p.b >> 31 & mod2),
               p.c + (p.c >> 31 & mod3));
  }
  inline crt operator+(const crt &p) const {
    return upd(crt(a + p.a - mod1, b + p.b - mod2, c + p.c - mod3));
  }
  inline crt operator-(const crt &p) const {
    return upd(crt(a - p.a, b - p.b, c - p.c));
  }
  inline crt operator*(const crt &p) const {
    return crt(1ll * a * p.a % mod1, 1ll * b * p.b % mod2,
               1ll * c * p.c % mod3);
  }
  inline int norm() {
    const long long x = 1ll * (b - a + mod2) % mod2 * inv_1 % mod2 * mod1 + a;
    return (1ll * (c - x % mod3 + mod3) % mod3 * inv_2 % mod3 *
                (mod_1_2 % mod) % mod +
            x) %
           mod;
  }
} wn[500005];
int rev[500005];
namespace ntt {
inline void install(int n) {
  for (int mid = 1; mid < n; mid <<= 1) {
    crt w = crt(qpow(G, mod1 / mid >> 1, mod1), qpow(G, mod2 / mid >> 1, mod2),
                qpow(G, mod3 / mid >> 1, mod3));
    wn[mid] = crt(1);
    for (int i = 1, iend = mid - 1; i <= iend; ++i)
      wn[mid + i] = wn[mid + i - 1] * w;
  }
}
int lim;
inline void init(int n) {
  for (lim = 1; lim < n; lim <<= 1)
    ;
  for (int i = 1, iend = lim - 1; i <= iend; ++i)
    rev[i] = rev[i >> 1] >> 1 | (lim >> 1 & -(i & 1));
}
inline void ntt(crt *a, int ty) {
  static crt b[500005];
  for (int i = 0, iend = lim - 1; i <= iend; ++i) b[i] = a[rev[i]];
  for (int mid = 1; mid < lim; mid <<= 1) {
    for (int i = 0; i < lim; i += mid << 1) {
      for (int j = 0, jend = mid - 1; j <= jend; ++j) {
        const crt x = b[i + j + mid] * wn[mid + j];
        b[i + j + mid] = b[i + j] - x;
        b[i + j] = b[i + j] + x;
      }
    }
  }
  if (!ty) {
    crt invlim = crt(qpow(lim, mod1 - 2, mod1), qpow(lim, mod2 - 2, mod2),
                     qpow(lim, mod3 - 2, mod3));
    for (int i = 0, iend = lim - 1; i <= iend; ++i) a[i] = b[i] * invlim;
    std::reverse(a + 1, a + lim);
  } else {
    for (int i = 0, iend = lim - 1; i <= iend; ++i) a[i] = b[i];
  }
}
inline void _ntt(crt *a, crt *b) {
  ntt(a, 1), ntt(b, 1);
  for (int i = 0, iend = lim - 1; i <= iend; ++i) a[i] = a[i] * b[i];
  ntt(a, 0);
}
}  // namespace ntt
crt a[500005], b[500005];
int n, k, fac[500005], inv[500005];
inline void init(int n) {
  fac[0] = 1;
  for (int i = 1, iend = n; i <= iend; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[n] = qpow(fac[n], mod - 2, mod);
  for (int i = n - 1, iend = 0; i >= iend; --i)
    inv[i] = inv[i + 1] * (i + 1ll) % mod;
}
inline void solve(int len) {
  if (len == 1) {
    a[0] = crt(0);
    for (int i = 1, iend = k; i <= iend; ++i) a[i] = crt(inv[i]);
    return;
  }
  solve(len >> 1);
  b[0] = crt(0);
  for (int i = 1, iend = k; i <= iend; ++i)
    b[i] = crt(1ll * a[i].norm() *
               qpow(2, 1ll * (len >> 1) * i % (mod - 1), mod) % mod);
  for (int i = k + 1, iend = ntt::lim - 1; i <= iend; ++i) a[i] = b[i] = crt(0);
  ntt::_ntt(a, b);
  if (len & 1) {
    b[0] = crt(0);
    for (int i = 1, iend = k; i <= iend; ++i) {
      int val = a[i].norm();
      a[i] = crt(1ll * val * qpow(2, i, mod) % mod);
      b[i] = crt(inv[i]);
    }
    for (int i = k + 1, iend = ntt::lim - 1; i <= iend; ++i)
      a[i] = b[i] = crt(0);
    ntt::_ntt(a, b);
  }
  for (int i = 0, iend = k; i <= iend; ++i) {
    int val = a[i].norm();
    a[i] = crt(val);
  }
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  std::cin >> n >> k;
  if (n > k) return std::cout << "0\n", 0;
  init(k);
  ntt::install(k + 10 << 2), ntt::init(k + 10 << 1);
  solve(n);
  int ans = 0;
  for (int i = 1, iend = k; i <= iend; ++i)
    ans = (ans + 1ll * a[i].norm() * fac[k] % mod * inv[k - i]) % mod;
  std::cout << ans << '\n';
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Let's define the transformation P of a sequence of integers a1, a2, ..., an as b1, b2, ..., bn, where bi = a1 | a2 | ... | ai for all i = 1, 2, ..., n, where | is the bitwise OR operation.

Vasya consequently applies the transformation P to all sequences of length n consisting of integers from 1 to 2k - 1 inclusive. He wants to know how many of these sequences have such property that their transformation is a strictly increasing sequence. Help him to calculate this number modulo 109 + 7.

Input

The only line of the input contains two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 30 000).

Output

Print a single integer — the answer to the problem modulo 109 + 7.

Examples

Input

1 2


Output

3


Input

2 3


Output

30


Input

3 3


Output

48

### Response

```cpp
#include <bits/stdc++.h>
inline int qpow(int x, int y, int mod, int ret = 1) {
  for (; y; y >>= 1, x = 1ll * x * x % mod)
    if (y & 1) ret = 1ll * ret * x % mod;
  return ret;
}
const int mod = 1e9 + 7;
const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
const long long mod_1_2 = 1ll * mod1 * mod2;
const int inv_1 = qpow(mod1, mod2 - 2, mod2),
          inv_2 = qpow(mod_1_2 % mod3, mod3 - 2, mod3);
struct crt {
  int a, b, c;
  crt() {}
  crt(int _a) { a = b = c = _a; }
  crt(int _a, int _b, int _c) { a = _a, b = _b, c = _c; }
  inline friend crt upd(const crt &p) {
    return crt(p.a + (p.a >> 31 & mod1), p.b + (p.b >> 31 & mod2),
               p.c + (p.c >> 31 & mod3));
  }
  inline crt operator+(const crt &p) const {
    return upd(crt(a + p.a - mod1, b + p.b - mod2, c + p.c - mod3));
  }
  inline crt operator-(const crt &p) const {
    return upd(crt(a - p.a, b - p.b, c - p.c));
  }
  inline crt operator*(const crt &p) const {
    return crt(1ll * a * p.a % mod1, 1ll * b * p.b % mod2,
               1ll * c * p.c % mod3);
  }
  inline int norm() {
    const long long x = 1ll * (b - a + mod2) % mod2 * inv_1 % mod2 * mod1 + a;
    return (1ll * (c - x % mod3 + mod3) % mod3 * inv_2 % mod3 *
                (mod_1_2 % mod) % mod +
            x) %
           mod;
  }
} wn[500005];
int rev[500005];
namespace ntt {
inline void install(int n) {
  for (int mid = 1; mid < n; mid <<= 1) {
    crt w = crt(qpow(G, mod1 / mid >> 1, mod1), qpow(G, mod2 / mid >> 1, mod2),
                qpow(G, mod3 / mid >> 1, mod3));
    wn[mid] = crt(1);
    for (int i = 1, iend = mid - 1; i <= iend; ++i)
      wn[mid + i] = wn[mid + i - 1] * w;
  }
}
int lim;
inline void init(int n) {
  for (lim = 1; lim < n; lim <<= 1)
    ;
  for (int i = 1, iend = lim - 1; i <= iend; ++i)
    rev[i] = rev[i >> 1] >> 1 | (lim >> 1 & -(i & 1));
}
inline void ntt(crt *a, int ty) {
  static crt b[500005];
  for (int i = 0, iend = lim - 1; i <= iend; ++i) b[i] = a[rev[i]];
  for (int mid = 1; mid < lim; mid <<= 1) {
    for (int i = 0; i < lim; i += mid << 1) {
      for (int j = 0, jend = mid - 1; j <= jend; ++j) {
        const crt x = b[i + j + mid] * wn[mid + j];
        b[i + j + mid] = b[i + j] - x;
        b[i + j] = b[i + j] + x;
      }
    }
  }
  if (!ty) {
    crt invlim = crt(qpow(lim, mod1 - 2, mod1), qpow(lim, mod2 - 2, mod2),
                     qpow(lim, mod3 - 2, mod3));
    for (int i = 0, iend = lim - 1; i <= iend; ++i) a[i] = b[i] * invlim;
    std::reverse(a + 1, a + lim);
  } else {
    for (int i = 0, iend = lim - 1; i <= iend; ++i) a[i] = b[i];
  }
}
inline void _ntt(crt *a, crt *b) {
  ntt(a, 1), ntt(b, 1);
  for (int i = 0, iend = lim - 1; i <= iend; ++i) a[i] = a[i] * b[i];
  ntt(a, 0);
}
}  // namespace ntt
crt a[500005], b[500005];
int n, k, fac[500005], inv[500005];
inline void init(int n) {
  fac[0] = 1;
  for (int i = 1, iend = n; i <= iend; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[n] = qpow(fac[n], mod - 2, mod);
  for (int i = n - 1, iend = 0; i >= iend; --i)
    inv[i] = inv[i + 1] * (i + 1ll) % mod;
}
inline void solve(int len) {
  if (len == 1) {
    a[0] = crt(0);
    for (int i = 1, iend = k; i <= iend; ++i) a[i] = crt(inv[i]);
    return;
  }
  solve(len >> 1);
  b[0] = crt(0);
  for (int i = 1, iend = k; i <= iend; ++i)
    b[i] = crt(1ll * a[i].norm() *
               qpow(2, 1ll * (len >> 1) * i % (mod - 1), mod) % mod);
  for (int i = k + 1, iend = ntt::lim - 1; i <= iend; ++i) a[i] = b[i] = crt(0);
  ntt::_ntt(a, b);
  if (len & 1) {
    b[0] = crt(0);
    for (int i = 1, iend = k; i <= iend; ++i) {
      int val = a[i].norm();
      a[i] = crt(1ll * val * qpow(2, i, mod) % mod);
      b[i] = crt(inv[i]);
    }
    for (int i = k + 1, iend = ntt::lim - 1; i <= iend; ++i)
      a[i] = b[i] = crt(0);
    ntt::_ntt(a, b);
  }
  for (int i = 0, iend = k; i <= iend; ++i) {
    int val = a[i].norm();
    a[i] = crt(val);
  }
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  std::cin >> n >> k;
  if (n > k) return std::cout << "0\n", 0;
  init(k);
  ntt::install(k + 10 << 2), ntt::init(k + 10 << 1);
  solve(n);
  int ans = 0;
  for (int i = 1, iend = k; i <= iend; ++i)
    ans = (ans + 1ll * a[i].norm() * fac[k] % mod * inv[k - i]) % mod;
  std::cout << ans << '\n';
  return 0;
}

```