#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int N = 65536, L = 15, MASK = (1 << L) - 1;
complex<double> w[N];
void FFTInit() {
  for (int i = 0; i < N; ++i) {
    w[i] = complex<double>(cos(2 * i * PI / N), sin(2 * i * PI / N));
  }
}
void FFT(complex<double> p[], int n) {
  for (int i = 1, j = 0; i < n - 1; ++i) {
    for (int s = n; j ^= s >>= 1, ~j & s;)
      ;
    if (i < j) swap(p[i], p[j]);
  }
  for (int d = 0; (1 << d) < n; ++d) {
    int m = 1 << d, m2 = m * 2, rm = n >> (d + 1);
    for (int i = 0; i < n; i += m2) {
      for (int j = 0; j < m; ++j) {
        complex<double> &p1 = p[i + j + m], &p2 = p[i + j];
        complex<double> t = w[rm * j] * p1;
        p1 = p2 - t, p2 = p2 + t;
      }
    }
  }
}
complex<double> A[N], B[N], C[N], D[N];
void mul(int a[N], int b[N]) {
  for (int i = 0; i < N; ++i) {
    A[i] = complex<double>(a[i] >> L, a[i] & MASK);
    B[i] = complex<double>(b[i] >> L, b[i] & MASK);
  }
  FFT(A, N);
  FFT(B, N);
  for (int i = 0; i < N; ++i) {
    int j = (N - i) % N;
    complex<double> da = (A[i] - conj(A[j])) * complex<double>(0, -0.5);
    complex<double> db = (A[i] + conj(A[j])) * complex<double>(0.5, 0);
    complex<double> dc = (B[i] - conj(B[j])) * complex<double>(0, -0.5);
    complex<double> dd = (B[i] + conj(B[j])) * complex<double>(0.5, 0);
    C[j] = da * dd + da * dc * complex<double>(0, 1);
    D[j] = db * dd + db * dc * complex<double>(0, 1);
  }
  FFT(C, N);
  FFT(D, N);
  for (int i = 0; i < N; ++i) {
    long long da = (long long)(C[i].imag() / N + 0.5) % MOD;
    long long db = (long long)(C[i].real() / N + 0.5) % MOD;
    long long dc = (long long)(D[i].imag() / N + 0.5) % MOD;
    long long dd = (long long)(D[i].real() / N + 0.5) % MOD;
    a[i] = ((dd << (L * 2)) + ((db + dc) << L) + da) % MOD;
  }
}
int mpow(int x, long long n) {
  int res = 1;
  while (n) {
    if (n & 1) res = 1LL * res * x % MOD;
    x = 1LL * x * x % MOD;
    n >>= 1;
  }
  return res;
}
int m;
void clean(int a[N]) {
  for (int i = m + 1; i < N; ++i) a[i] = 0;
}
void shift(int a[N], long long x) {
  for (int i = 0; i < N; ++i)
    a[i] = 1LL * a[i] * mpow(2, x % (MOD - 1) * i % (MOD - 1)) % MOD;
}
void mpow(int x[N], long long n) {
  static int res[N], y[N];
  memset(res, 0, sizeof(res));
  res[0] = 1;
  long long len = 1;
  while (n) {
    if (n & 1) {
      shift(res, len);
      mul(res, x);
      clean(res);
    }
    n >>= 1;
    for (int i = 0; i < N; ++i) y[i] = x[i];
    shift(x, len);
    mul(x, y);
    len = len * 2;
    clean(x);
  }
  for (int i = 1; i <= m; ++i) x[i] = res[i];
}
int main() {
  FFTInit();
  long long n;
  cin >> n >> m;
  if (n > m) return 0 * puts("0");
  static int a[N];
  int tmp = 1;
  for (int i = 1; i <= m; ++i) {
    tmp = 1LL * tmp * i % MOD;
    a[i] = mpow(tmp, MOD - 2);
  }
  mpow(a, n);
  tmp = 1;
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    tmp = 1LL * tmp * (m - i + 1) % MOD;
    (ans += 1LL * a[i] * tmp % MOD) %= MOD;
  }
  cout << ans << endl;
}

### Prompt

Please formulate 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>
using namespace std;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int N = 65536, L = 15, MASK = (1 << L) - 1;
complex<double> w[N];
void FFTInit() {
  for (int i = 0; i < N; ++i) {
    w[i] = complex<double>(cos(2 * i * PI / N), sin(2 * i * PI / N));
  }
}
void FFT(complex<double> p[], int n) {
  for (int i = 1, j = 0; i < n - 1; ++i) {
    for (int s = n; j ^= s >>= 1, ~j & s;)
      ;
    if (i < j) swap(p[i], p[j]);
  }
  for (int d = 0; (1 << d) < n; ++d) {
    int m = 1 << d, m2 = m * 2, rm = n >> (d + 1);
    for (int i = 0; i < n; i += m2) {
      for (int j = 0; j < m; ++j) {
        complex<double> &p1 = p[i + j + m], &p2 = p[i + j];
        complex<double> t = w[rm * j] * p1;
        p1 = p2 - t, p2 = p2 + t;
      }
    }
  }
}
complex<double> A[N], B[N], C[N], D[N];
void mul(int a[N], int b[N]) {
  for (int i = 0; i < N; ++i) {
    A[i] = complex<double>(a[i] >> L, a[i] & MASK);
    B[i] = complex<double>(b[i] >> L, b[i] & MASK);
  }
  FFT(A, N);
  FFT(B, N);
  for (int i = 0; i < N; ++i) {
    int j = (N - i) % N;
    complex<double> da = (A[i] - conj(A[j])) * complex<double>(0, -0.5);
    complex<double> db = (A[i] + conj(A[j])) * complex<double>(0.5, 0);
    complex<double> dc = (B[i] - conj(B[j])) * complex<double>(0, -0.5);
    complex<double> dd = (B[i] + conj(B[j])) * complex<double>(0.5, 0);
    C[j] = da * dd + da * dc * complex<double>(0, 1);
    D[j] = db * dd + db * dc * complex<double>(0, 1);
  }
  FFT(C, N);
  FFT(D, N);
  for (int i = 0; i < N; ++i) {
    long long da = (long long)(C[i].imag() / N + 0.5) % MOD;
    long long db = (long long)(C[i].real() / N + 0.5) % MOD;
    long long dc = (long long)(D[i].imag() / N + 0.5) % MOD;
    long long dd = (long long)(D[i].real() / N + 0.5) % MOD;
    a[i] = ((dd << (L * 2)) + ((db + dc) << L) + da) % MOD;
  }
}
int mpow(int x, long long n) {
  int res = 1;
  while (n) {
    if (n & 1) res = 1LL * res * x % MOD;
    x = 1LL * x * x % MOD;
    n >>= 1;
  }
  return res;
}
int m;
void clean(int a[N]) {
  for (int i = m + 1; i < N; ++i) a[i] = 0;
}
void shift(int a[N], long long x) {
  for (int i = 0; i < N; ++i)
    a[i] = 1LL * a[i] * mpow(2, x % (MOD - 1) * i % (MOD - 1)) % MOD;
}
void mpow(int x[N], long long n) {
  static int res[N], y[N];
  memset(res, 0, sizeof(res));
  res[0] = 1;
  long long len = 1;
  while (n) {
    if (n & 1) {
      shift(res, len);
      mul(res, x);
      clean(res);
    }
    n >>= 1;
    for (int i = 0; i < N; ++i) y[i] = x[i];
    shift(x, len);
    mul(x, y);
    len = len * 2;
    clean(x);
  }
  for (int i = 1; i <= m; ++i) x[i] = res[i];
}
int main() {
  FFTInit();
  long long n;
  cin >> n >> m;
  if (n > m) return 0 * puts("0");
  static int a[N];
  int tmp = 1;
  for (int i = 1; i <= m; ++i) {
    tmp = 1LL * tmp * i % MOD;
    a[i] = mpow(tmp, MOD - 2);
  }
  mpow(a, n);
  tmp = 1;
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    tmp = 1LL * tmp * (m - i + 1) % MOD;
    (ans += 1LL * a[i] * tmp % MOD) %= MOD;
  }
  cout << ans << endl;
}

```