#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
int r[(1 << 16) + 5], n2;
vector<complex<double> > w[30], iw[30];
void FFT(vector<complex<double> > &a, int opt) {
  for (int i = 1; i <= n2 - 1; i++)
    if (r[i] > i) swap(a[i], a[r[i]]);
  for (int step = 1, pw = 0; step < n2; step <<= 1, pw++) {
    for (int step2 = step << 1, i = 0; i < n2; i += step2) {
      for (int j = 0; j <= step - 1; j++) {
        complex<double> wj = opt == 1 ? w[pw][j] : iw[pw][j];
        complex<double> even = a[i + j];
        complex<double> odd = a[i + j + step];
        complex<double> tmp = wj * odd;
        a[i + j] = even + tmp;
        a[i + j + step] = even - tmp;
      }
    }
  }
}
int k;
void work(vector<complex<double> > &a, vector<complex<double> > &b,
          vector<int> &ans, int w) {
  vector<complex<double> > tmp(n2);
  for (int i = 0; i <= n2 - 1; i++) tmp[i] = a[i] * b[i];
  FFT(tmp, -1);
  for (int i = 0; i <= k; i++)
    ans[i] = (ans[i] + (long long)(tmp[i].real() / n2 + 0.5) % 1000000007 * w) %
             1000000007;
}
int M;
vector<int> mult(vector<int> &a, vector<int> &b) {
  vector<complex<double> > A(n2), B(n2), C(n2), D(n2);
  for (int i = 0; i <= n2 - 1; i++) A[i] = a[i] / M, B[i] = a[i] % M;
  for (int i = 0; i <= n2 - 1; i++) C[i] = b[i] / M, D[i] = b[i] % M;
  FFT(A, 1);
  FFT(B, 1);
  FFT(C, 1);
  FFT(D, 1);
  vector<int> c(n2, 0);
  work(A, C, c, 1ll * M * M % 1000000007);
  work(B, D, c, 1);
  work(A, D, c, M);
  work(B, C, c, M);
  return c;
}
long long fac[(1 << 16) + 5], inv[(1 << 16) + 5], ifac[(1 << 16) + 5];
vector<int> ONE;
long long qp(long long a, int pw) {
  long long res = 1;
  while (pw) {
    if (pw & 1) res = res * a % 1000000007;
    a = a * a % 1000000007;
    pw >>= 1;
  }
  return res;
}
vector<int> cal(int n) {
  if (n == 1) return ONE;
  vector<int> A = cal(n / 2), B = A;
  for (int i = 1; i <= k; i++)
    A[i] = 1ll * A[i] * qp(2, n / 2 * i) % 1000000007;
  A = mult(A, B);
  if (n & 1) {
    for (int i = 1; i <= k; i++) A[i] = 1ll * A[i] * qp(2, i) % 1000000007;
    A = mult(A, ONE);
  }
  return A;
}
long long C(int n, int m) {
  return fac[n] * ifac[m] % 1000000007 * ifac[n - m] % 1000000007;
}
int main() {
  inv[1] = fac[0] = ifac[0] = 1;
  for (int i = 2; i <= (1 << 16); i++)
    inv[i] = inv[1000000007 % i] * (1000000007 - 1000000007 / i) % 1000000007;
  for (int i = 1; i <= (1 << 16); i++) fac[i] = fac[i - 1] * i % 1000000007;
  for (int i = 1; i <= (1 << 16); i++)
    ifac[i] = ifac[i - 1] * inv[i] % 1000000007;
  long long n;
  scanf("%I64d%d", &n, &k);
  if (n > k)
    puts("0");
  else {
    M = sqrt(1000000007) + 0.5;
    int l = 0;
    for (n2 = 1; n2 < k * 2 + 1; n2 <<= 1) {
      int step = 1 << l;
      w[l].resize(step);
      iw[l].resize(step);
      for (int j = 0; j <= step - 1; j++) {
        double sita = pi * j / step;
        w[l][j].real(cos(sita));
        w[l][j].imag(sin(sita));
        iw[l][j].real(cos(-sita));
        iw[l][j].imag(sin(-sita));
      }
      l++;
    }
    for (int i = 1; i <= n2 - 1; i++)
      r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
    ONE.resize(n2, 0);
    for (int i = 1; i <= k; i++) ONE[i] = ifac[i];
    vector<int> res = cal(n);
    long long ans = 0;
    for (int i = 1; i <= k; i++)
      ans = (ans + C(k, i) * res[i] % 1000000007 * fac[i]) % 1000000007;
    printf("%I64d\n", ans);
  }
  return 0;
}

### 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 double pi = acos(-1.0);
int r[(1 << 16) + 5], n2;
vector<complex<double> > w[30], iw[30];
void FFT(vector<complex<double> > &a, int opt) {
  for (int i = 1; i <= n2 - 1; i++)
    if (r[i] > i) swap(a[i], a[r[i]]);
  for (int step = 1, pw = 0; step < n2; step <<= 1, pw++) {
    for (int step2 = step << 1, i = 0; i < n2; i += step2) {
      for (int j = 0; j <= step - 1; j++) {
        complex<double> wj = opt == 1 ? w[pw][j] : iw[pw][j];
        complex<double> even = a[i + j];
        complex<double> odd = a[i + j + step];
        complex<double> tmp = wj * odd;
        a[i + j] = even + tmp;
        a[i + j + step] = even - tmp;
      }
    }
  }
}
int k;
void work(vector<complex<double> > &a, vector<complex<double> > &b,
          vector<int> &ans, int w) {
  vector<complex<double> > tmp(n2);
  for (int i = 0; i <= n2 - 1; i++) tmp[i] = a[i] * b[i];
  FFT(tmp, -1);
  for (int i = 0; i <= k; i++)
    ans[i] = (ans[i] + (long long)(tmp[i].real() / n2 + 0.5) % 1000000007 * w) %
             1000000007;
}
int M;
vector<int> mult(vector<int> &a, vector<int> &b) {
  vector<complex<double> > A(n2), B(n2), C(n2), D(n2);
  for (int i = 0; i <= n2 - 1; i++) A[i] = a[i] / M, B[i] = a[i] % M;
  for (int i = 0; i <= n2 - 1; i++) C[i] = b[i] / M, D[i] = b[i] % M;
  FFT(A, 1);
  FFT(B, 1);
  FFT(C, 1);
  FFT(D, 1);
  vector<int> c(n2, 0);
  work(A, C, c, 1ll * M * M % 1000000007);
  work(B, D, c, 1);
  work(A, D, c, M);
  work(B, C, c, M);
  return c;
}
long long fac[(1 << 16) + 5], inv[(1 << 16) + 5], ifac[(1 << 16) + 5];
vector<int> ONE;
long long qp(long long a, int pw) {
  long long res = 1;
  while (pw) {
    if (pw & 1) res = res * a % 1000000007;
    a = a * a % 1000000007;
    pw >>= 1;
  }
  return res;
}
vector<int> cal(int n) {
  if (n == 1) return ONE;
  vector<int> A = cal(n / 2), B = A;
  for (int i = 1; i <= k; i++)
    A[i] = 1ll * A[i] * qp(2, n / 2 * i) % 1000000007;
  A = mult(A, B);
  if (n & 1) {
    for (int i = 1; i <= k; i++) A[i] = 1ll * A[i] * qp(2, i) % 1000000007;
    A = mult(A, ONE);
  }
  return A;
}
long long C(int n, int m) {
  return fac[n] * ifac[m] % 1000000007 * ifac[n - m] % 1000000007;
}
int main() {
  inv[1] = fac[0] = ifac[0] = 1;
  for (int i = 2; i <= (1 << 16); i++)
    inv[i] = inv[1000000007 % i] * (1000000007 - 1000000007 / i) % 1000000007;
  for (int i = 1; i <= (1 << 16); i++) fac[i] = fac[i - 1] * i % 1000000007;
  for (int i = 1; i <= (1 << 16); i++)
    ifac[i] = ifac[i - 1] * inv[i] % 1000000007;
  long long n;
  scanf("%I64d%d", &n, &k);
  if (n > k)
    puts("0");
  else {
    M = sqrt(1000000007) + 0.5;
    int l = 0;
    for (n2 = 1; n2 < k * 2 + 1; n2 <<= 1) {
      int step = 1 << l;
      w[l].resize(step);
      iw[l].resize(step);
      for (int j = 0; j <= step - 1; j++) {
        double sita = pi * j / step;
        w[l][j].real(cos(sita));
        w[l][j].imag(sin(sita));
        iw[l][j].real(cos(-sita));
        iw[l][j].imag(sin(-sita));
      }
      l++;
    }
    for (int i = 1; i <= n2 - 1; i++)
      r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
    ONE.resize(n2, 0);
    for (int i = 1; i <= k; i++) ONE[i] = ifac[i];
    vector<int> res = cal(n);
    long long ans = 0;
    for (int i = 1; i <= k; i++)
      ans = (ans + C(k, i) * res[i] % 1000000007 * fac[i]) % 1000000007;
    printf("%I64d\n", ans);
  }
  return 0;
}

```