#include <bits/stdc++.h>
using namespace std;
const int N = 3 * (1e4) + 10, MOD = 32768, p = 1e9 + 7;
const double pi = acos(-1);
int ret[N], base[N], fac[N], invfac[N];
long long n, m;
int len, ans;
int plu(int x, int y) { return (1LL * x + y) % p; }
int mul(int x, int y) { return 1LL * x * y % p; }
struct cmplx {
  double a, b;
  cmplx() {}
  cmplx(double a1, double b1) {
    a = a1;
    b = b1;
  }
  void init() {
    a = 0;
    b = 0;
  }
  friend cmplx operator+(cmplx x, cmplx y) {
    return cmplx(x.a + y.a, x.b + y.b);
  }
  friend cmplx operator-(cmplx x, cmplx y) {
    return cmplx(x.a - y.a, x.b - y.b);
  }
  friend cmplx operator*(cmplx x, cmplx y) {
    return cmplx(x.a * y.a - x.b * y.b, x.a * y.b + x.b * y.a);
  }
};
namespace FFT {
const int N = 65536 + 10, TOP = 19;
cmplx A1[N], A2[N], B1[N], B2[N], W[TOP + 1][N];
int rev[N], vis[TOP + 1], ans[N];
int len;
int get_val(cmplx x) { return ((long long)round(x.a) % p); }
void get_len(int n) {
  for (int i = 0; i < len; ++i)
    A1[i].init(), A2[i].init(), B1[i].init(), B2[i].init();
  int bit = 0;
  for (len = 1; len <= n; len <<= 1, ++bit)
    ;
  rev[0] = 0;
  for (int i = 1; i < len; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
  for (int i = 2, k = 0; i <= len; i <<= 1, ++k) {
    if (vis[k]) continue;
    for (int j = 0; j < (i >> 1); ++j)
      W[k][j] = cmplx(cos(j * pi / (i / 2)), sin(j * pi / (i / 2)));
    vis[k] = 1;
  }
}
void fft(cmplx *a, int op) {
  for (int i = 0; i < len; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  cmplx u, v, w;
  for (int step = 2, k = 0; step <= len; step <<= 1, ++k) {
    for (int st = 0; st < len; st += step) {
      for (int i = 0; i < (step >> 1); ++i) {
        w = W[k][i];
        w.b *= op;
        v = a[st + i + (step >> 1)] * w;
        u = a[st + i];
        a[st + i] = u + v;
        a[st + i + (step >> 1)] = u - v;
      }
    }
  }
  if (op == -1)
    for (int i = 0; i < len; ++i) a[i].a /= len;
}
void work(int *a, int *b, int n, int val) {
  cmplx a1, a2, b1, b2;
  int tmp = 1;
  for (int i = 0; i < len; ++i)
    A1[i].init(), A2[i].init(), B1[i].init(), B2[i].init();
  for (int i = 0; i <= n; ++i)
    A1[i] = cmplx(mul(a[i], tmp) / MOD, 0),
    A2[i] = cmplx(mul(a[i], tmp) % MOD, 0), tmp = mul(tmp, val);
  for (int i = 0; i <= n; ++i)
    B1[i] = cmplx(b[i] / MOD, 0), B2[i] = cmplx(b[i] % MOD, 0);
  fft(A1, 1);
  fft(A2, 1);
  fft(B1, 1);
  fft(B2, 1);
  for (int i = 0; i < len; ++i) {
    a1 = A1[i];
    a2 = A2[i];
    b1 = B1[i];
    b2 = B2[i];
    A1[i] = a1 * b1;
    A2[i] = a1 * b2 + a2 * b1;
    B2[i] = a2 * b2;
  }
  fft(A1, -1);
  fft(A2, -1);
  fft(B1, -1);
  fft(B2, -1);
  for (int i = 0; i < len; ++i) {
    ans[i] = 1LL * get_val(A1[i]) * MOD % p * MOD % p;
    ans[i] = plu(ans[i], 1LL * get_val(A2[i]) * MOD % p);
    ans[i] = plu(ans[i], get_val(B2[i]) % p);
  }
}
}  // namespace FFT
int ksm(int x, int y) {
  int ret = 1, base = x;
  for (; y; y >>= 1, base = mul(base, base))
    if (y & 1) ret = mul(ret, base);
  return ret;
}
int C(int n, int m) {
  return n < m ? 0 : 1LL * fac[n] * invfac[m] % p * invfac[n - m] % p;
}
void prework(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
  invfac[n] = ksm(fac[n], p - 2);
  for (int i = n - 1; i >= 0; --i) invfac[i] = mul(invfac[i + 1], i + 1);
}
void solve() {
  int pw2 = 2;
  memset(ret, 0, sizeof(ret));
  ret[0] = 1;
  len = m;
  FFT::get_len(len + len);
  for (int i = 1; i <= len; ++i) base[i] = invfac[i];
  while (n) {
    if (n & 1) {
      FFT::work(ret, base, len, pw2);
      for (int i = 0; i <= len; ++i) ret[i] = FFT::ans[i];
    }
    FFT::work(base, base, len, pw2);
    for (int i = 0; i <= len; ++i) base[i] = FFT::ans[i];
    pw2 = mul(pw2, pw2);
    n >>= 1;
  }
  ans = 0;
  for (int i = 0; i <= len; ++i) ret[i] = mul(ret[i], fac[i]);
  for (int i = n; i <= m; ++i) ans = plu(ans, mul(C(m, i), ret[i]));
  printf("%d\n", ans);
}
int main() {
  scanf("%lld%lld", &n, &m);
  if (n > m) {
    printf("0\n");
    return 0;
  }
  prework(m);
  solve();
}

### Prompt

Develop a solution in cpp to the problem described below:

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>
using namespace std;
const int N = 3 * (1e4) + 10, MOD = 32768, p = 1e9 + 7;
const double pi = acos(-1);
int ret[N], base[N], fac[N], invfac[N];
long long n, m;
int len, ans;
int plu(int x, int y) { return (1LL * x + y) % p; }
int mul(int x, int y) { return 1LL * x * y % p; }
struct cmplx {
  double a, b;
  cmplx() {}
  cmplx(double a1, double b1) {
    a = a1;
    b = b1;
  }
  void init() {
    a = 0;
    b = 0;
  }
  friend cmplx operator+(cmplx x, cmplx y) {
    return cmplx(x.a + y.a, x.b + y.b);
  }
  friend cmplx operator-(cmplx x, cmplx y) {
    return cmplx(x.a - y.a, x.b - y.b);
  }
  friend cmplx operator*(cmplx x, cmplx y) {
    return cmplx(x.a * y.a - x.b * y.b, x.a * y.b + x.b * y.a);
  }
};
namespace FFT {
const int N = 65536 + 10, TOP = 19;
cmplx A1[N], A2[N], B1[N], B2[N], W[TOP + 1][N];
int rev[N], vis[TOP + 1], ans[N];
int len;
int get_val(cmplx x) { return ((long long)round(x.a) % p); }
void get_len(int n) {
  for (int i = 0; i < len; ++i)
    A1[i].init(), A2[i].init(), B1[i].init(), B2[i].init();
  int bit = 0;
  for (len = 1; len <= n; len <<= 1, ++bit)
    ;
  rev[0] = 0;
  for (int i = 1; i < len; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
  for (int i = 2, k = 0; i <= len; i <<= 1, ++k) {
    if (vis[k]) continue;
    for (int j = 0; j < (i >> 1); ++j)
      W[k][j] = cmplx(cos(j * pi / (i / 2)), sin(j * pi / (i / 2)));
    vis[k] = 1;
  }
}
void fft(cmplx *a, int op) {
  for (int i = 0; i < len; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  cmplx u, v, w;
  for (int step = 2, k = 0; step <= len; step <<= 1, ++k) {
    for (int st = 0; st < len; st += step) {
      for (int i = 0; i < (step >> 1); ++i) {
        w = W[k][i];
        w.b *= op;
        v = a[st + i + (step >> 1)] * w;
        u = a[st + i];
        a[st + i] = u + v;
        a[st + i + (step >> 1)] = u - v;
      }
    }
  }
  if (op == -1)
    for (int i = 0; i < len; ++i) a[i].a /= len;
}
void work(int *a, int *b, int n, int val) {
  cmplx a1, a2, b1, b2;
  int tmp = 1;
  for (int i = 0; i < len; ++i)
    A1[i].init(), A2[i].init(), B1[i].init(), B2[i].init();
  for (int i = 0; i <= n; ++i)
    A1[i] = cmplx(mul(a[i], tmp) / MOD, 0),
    A2[i] = cmplx(mul(a[i], tmp) % MOD, 0), tmp = mul(tmp, val);
  for (int i = 0; i <= n; ++i)
    B1[i] = cmplx(b[i] / MOD, 0), B2[i] = cmplx(b[i] % MOD, 0);
  fft(A1, 1);
  fft(A2, 1);
  fft(B1, 1);
  fft(B2, 1);
  for (int i = 0; i < len; ++i) {
    a1 = A1[i];
    a2 = A2[i];
    b1 = B1[i];
    b2 = B2[i];
    A1[i] = a1 * b1;
    A2[i] = a1 * b2 + a2 * b1;
    B2[i] = a2 * b2;
  }
  fft(A1, -1);
  fft(A2, -1);
  fft(B1, -1);
  fft(B2, -1);
  for (int i = 0; i < len; ++i) {
    ans[i] = 1LL * get_val(A1[i]) * MOD % p * MOD % p;
    ans[i] = plu(ans[i], 1LL * get_val(A2[i]) * MOD % p);
    ans[i] = plu(ans[i], get_val(B2[i]) % p);
  }
}
}  // namespace FFT
int ksm(int x, int y) {
  int ret = 1, base = x;
  for (; y; y >>= 1, base = mul(base, base))
    if (y & 1) ret = mul(ret, base);
  return ret;
}
int C(int n, int m) {
  return n < m ? 0 : 1LL * fac[n] * invfac[m] % p * invfac[n - m] % p;
}
void prework(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
  invfac[n] = ksm(fac[n], p - 2);
  for (int i = n - 1; i >= 0; --i) invfac[i] = mul(invfac[i + 1], i + 1);
}
void solve() {
  int pw2 = 2;
  memset(ret, 0, sizeof(ret));
  ret[0] = 1;
  len = m;
  FFT::get_len(len + len);
  for (int i = 1; i <= len; ++i) base[i] = invfac[i];
  while (n) {
    if (n & 1) {
      FFT::work(ret, base, len, pw2);
      for (int i = 0; i <= len; ++i) ret[i] = FFT::ans[i];
    }
    FFT::work(base, base, len, pw2);
    for (int i = 0; i <= len; ++i) base[i] = FFT::ans[i];
    pw2 = mul(pw2, pw2);
    n >>= 1;
  }
  ans = 0;
  for (int i = 0; i <= len; ++i) ret[i] = mul(ret[i], fac[i]);
  for (int i = n; i <= m; ++i) ans = plu(ans, mul(C(m, i), ret[i]));
  printf("%d\n", ans);
}
int main() {
  scanf("%lld%lld", &n, &m);
  if (n > m) {
    printf("0\n");
    return 0;
  }
  prework(m);
  solve();
}

```