#include <bits/stdc++.h>
inline int in() {
  int k = 0;
  char ch = getchar();
  while (ch < '-') ch = getchar();
  while (ch > '-') k = k * 10 + ch - '0', ch = getchar();
  return k;
}
const int N = 1e5 + 5, YL = 1e9 + 7;
const long double PI = acos(-1);
int a[N], b[N], c[N];
inline int MO(const int &a) { return a >= YL ? a - YL : a; }
inline int ksm(int a, int k) {
  int r = 1;
  while (k) {
    if (k & 1) r = 1ll * r * a % YL;
    a = 1ll * a * a % YL, k >>= 1;
  }
  return r;
}
int rev[N];
inline void get_rev(int len) {
  for (int i = 0; i < len; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
}
struct E {
  double x, y;
  E() {}
  E(double a, double b) : x(a), y(b) {}
  E operator=(const int &a) {
    x = a, y = 0;
    return *this;
  }
  E conj() { return E(x, -y); }
} omg[N];
E operator+(const E &a, const E &b) { return E(a.x + b.x, a.y + b.y); }
E operator-(const E &a, const E &b) { return E(a.x - b.x, a.y - b.y); }
E operator*(const E &a, const E &b) {
  return E(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline void get_omg(int len) {
  for (int i = 0; i < len; ++i)
    omg[i] = E(cos(PI * i / len), sin(PI * i / len));
}
inline void fft(E *a, int len) {
  for (int i = 0; i < len; ++i)
    if (i < rev[i]) std::swap(a[i], a[rev[i]]);
  for (int st = 2, m = 1; st <= len; st <<= 1, m <<= 1)
    for (E *p = a, x, y; p != a + len; p += st)
      for (int k = 0; k < m; ++k)
        x = p[k], y = omg[len / m * k] * p[k + m], p[k] = x + y,
        p[k + m] = x - y;
}
int fac[N], fnv[N], ans[N], g[N], res[N], pw[N];
inline int C(int x, int y) {
  return y > x ? 0 : 1ll * fac[x] * fnv[y] % YL * fnv[x - y] % YL;
}
inline void mul(int *_A, int *B, int *C, int len, int y) {
  static int A[N];
  for (int i = 0; i < len; ++i) A[i] = 1ll * _A[i] * ksm(pw[i], y) % YL;
  for (int i = len >> 1; i < len; ++i) B[i] = A[i] = 0;
  static E a[N], b[N], dfta[N], dftb[N], dftc[N], dftd[N];
  for (int i = 0; i < len; ++i) a[i] = E(A[i] & 32767, A[i] >> 15);
  for (int i = 0; i < len; ++i) b[i] = E(B[i] & 32767, B[i] >> 15);
  fft(a, len), fft(b, len);
  for (int i = 0; i < len; ++i) {
    int j = (len - i) & (len - 1);
    E da, db, dc, dd;
    da = (a[i] + a[j].conj()) * E(0.5, 0);
    db = (a[i] - a[j].conj()) * E(0, -0.5);
    dc = (b[i] + b[j].conj()) * E(0.5, 0);
    dd = (b[i] - b[j].conj()) * E(0, -0.5);
    dfta[j] = da * dc, dftb[j] = da * dd, dftc[j] = db * dc, dftd[j] = db * dd;
  }
  for (int i = 0; i < len; ++i) a[i] = dfta[i] + dftb[i] * E(0, 1);
  for (int i = 0; i < len; ++i) b[i] = dftc[i] + dftd[i] * E(0, 1);
  fft(a, len), fft(b, len);
  for (int i = 0; i < len; ++i) {
    int da = (long long)(a[i].x / len + 0.5) % YL;
    int db = (long long)(a[i].y / len + 0.5) % YL;
    int dc = (long long)(b[i].x / len + 0.5) % YL;
    int dd = (long long)(b[i].y / len + 0.5) % YL;
    C[i] = (da + ((long long)(db + dc) << 15) + ((long long)dd << 30)) % YL;
  }
}
void work(int n, int len, int k) {
  fac[0] = pw[0] = 1;
  for (int i = 1; i <= len; ++i) fac[i] = 1ll * fac[i - 1] * i % YL;
  fnv[len] = ksm(fac[len], YL - 2);
  for (int i = len; i >= 1; --i) fnv[i - 1] = 1ll * fnv[i] * i % YL;
  for (int i = 1; i <= len; ++i) pw[i] = MO(pw[i - 1] << 1);
  for (int i = 1; i <= k; ++i) res[i] = fnv[i];
  ans[0] = 1;
  int t = n, y = 1;
  while (t) {
    if (t & 1) mul(ans, res, ans, len, y);
    mul(res, res, res, len, y), t >>= 1, y <<= 1;
  }
  int ret = 0;
  for (int i = n; i <= k; ++i)
    ret = (1ll * ans[i] * fac[i] % YL * C(k, i) + ret) % YL;
  printf("%d\n", ret);
}
int main() {
  long long n, k;
  scanf("%lld%lld", &n, &k);
  if (n > k) return puts("0"), 0;
  int len = 1;
  while (len <= k << 1) len <<= 1;
  get_rev(len);
  get_omg(len);
  work(n, len, k);
  return 0;
}

### Prompt

Your task is to create a cpp solution 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 in() {
  int k = 0;
  char ch = getchar();
  while (ch < '-') ch = getchar();
  while (ch > '-') k = k * 10 + ch - '0', ch = getchar();
  return k;
}
const int N = 1e5 + 5, YL = 1e9 + 7;
const long double PI = acos(-1);
int a[N], b[N], c[N];
inline int MO(const int &a) { return a >= YL ? a - YL : a; }
inline int ksm(int a, int k) {
  int r = 1;
  while (k) {
    if (k & 1) r = 1ll * r * a % YL;
    a = 1ll * a * a % YL, k >>= 1;
  }
  return r;
}
int rev[N];
inline void get_rev(int len) {
  for (int i = 0; i < len; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
}
struct E {
  double x, y;
  E() {}
  E(double a, double b) : x(a), y(b) {}
  E operator=(const int &a) {
    x = a, y = 0;
    return *this;
  }
  E conj() { return E(x, -y); }
} omg[N];
E operator+(const E &a, const E &b) { return E(a.x + b.x, a.y + b.y); }
E operator-(const E &a, const E &b) { return E(a.x - b.x, a.y - b.y); }
E operator*(const E &a, const E &b) {
  return E(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline void get_omg(int len) {
  for (int i = 0; i < len; ++i)
    omg[i] = E(cos(PI * i / len), sin(PI * i / len));
}
inline void fft(E *a, int len) {
  for (int i = 0; i < len; ++i)
    if (i < rev[i]) std::swap(a[i], a[rev[i]]);
  for (int st = 2, m = 1; st <= len; st <<= 1, m <<= 1)
    for (E *p = a, x, y; p != a + len; p += st)
      for (int k = 0; k < m; ++k)
        x = p[k], y = omg[len / m * k] * p[k + m], p[k] = x + y,
        p[k + m] = x - y;
}
int fac[N], fnv[N], ans[N], g[N], res[N], pw[N];
inline int C(int x, int y) {
  return y > x ? 0 : 1ll * fac[x] * fnv[y] % YL * fnv[x - y] % YL;
}
inline void mul(int *_A, int *B, int *C, int len, int y) {
  static int A[N];
  for (int i = 0; i < len; ++i) A[i] = 1ll * _A[i] * ksm(pw[i], y) % YL;
  for (int i = len >> 1; i < len; ++i) B[i] = A[i] = 0;
  static E a[N], b[N], dfta[N], dftb[N], dftc[N], dftd[N];
  for (int i = 0; i < len; ++i) a[i] = E(A[i] & 32767, A[i] >> 15);
  for (int i = 0; i < len; ++i) b[i] = E(B[i] & 32767, B[i] >> 15);
  fft(a, len), fft(b, len);
  for (int i = 0; i < len; ++i) {
    int j = (len - i) & (len - 1);
    E da, db, dc, dd;
    da = (a[i] + a[j].conj()) * E(0.5, 0);
    db = (a[i] - a[j].conj()) * E(0, -0.5);
    dc = (b[i] + b[j].conj()) * E(0.5, 0);
    dd = (b[i] - b[j].conj()) * E(0, -0.5);
    dfta[j] = da * dc, dftb[j] = da * dd, dftc[j] = db * dc, dftd[j] = db * dd;
  }
  for (int i = 0; i < len; ++i) a[i] = dfta[i] + dftb[i] * E(0, 1);
  for (int i = 0; i < len; ++i) b[i] = dftc[i] + dftd[i] * E(0, 1);
  fft(a, len), fft(b, len);
  for (int i = 0; i < len; ++i) {
    int da = (long long)(a[i].x / len + 0.5) % YL;
    int db = (long long)(a[i].y / len + 0.5) % YL;
    int dc = (long long)(b[i].x / len + 0.5) % YL;
    int dd = (long long)(b[i].y / len + 0.5) % YL;
    C[i] = (da + ((long long)(db + dc) << 15) + ((long long)dd << 30)) % YL;
  }
}
void work(int n, int len, int k) {
  fac[0] = pw[0] = 1;
  for (int i = 1; i <= len; ++i) fac[i] = 1ll * fac[i - 1] * i % YL;
  fnv[len] = ksm(fac[len], YL - 2);
  for (int i = len; i >= 1; --i) fnv[i - 1] = 1ll * fnv[i] * i % YL;
  for (int i = 1; i <= len; ++i) pw[i] = MO(pw[i - 1] << 1);
  for (int i = 1; i <= k; ++i) res[i] = fnv[i];
  ans[0] = 1;
  int t = n, y = 1;
  while (t) {
    if (t & 1) mul(ans, res, ans, len, y);
    mul(res, res, res, len, y), t >>= 1, y <<= 1;
  }
  int ret = 0;
  for (int i = n; i <= k; ++i)
    ret = (1ll * ans[i] * fac[i] % YL * C(k, i) + ret) % YL;
  printf("%d\n", ret);
}
int main() {
  long long n, k;
  scanf("%lld%lld", &n, &k);
  if (n > k) return puts("0"), 0;
  int len = 1;
  while (len <= k << 1) len <<= 1;
  get_rev(len);
  get_omg(len);
  work(n, len, k);
  return 0;
}

```