#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
struct Cp {
  double x, y;
  Cp(double _x = 0, double _y = 0) { x = _x, y = _y; }
  Cp operator+(const Cp &ch) { return Cp(x + ch.x, y + ch.y); }
  Cp operator-(const Cp &ch) { return Cp(x - ch.x, y - ch.y); }
  Cp operator*(const Cp &ch) {
    return Cp(x * ch.x - y * ch.y, x * ch.y + y * ch.x);
  }
} A[N], B[N], C[N], D[N], w, w0, tmp, wi[16][65536];
;
int M, l, r[N];
void FFT(Cp *A, int f) {
  for (int i = 0; i < M; i++)
    if (r[i] > i) swap(A[r[i]], A[i]);
  int gg = 0;
  for (int i = 1; i < M; i <<= 1) {
    w.x = cos(acos(-1.0) / i), w.y = sin(acos(-1.0) / i) * f;
    for (int j = 0; j < M; j += (i << 1)) {
      for (int k = 0; k < i; k++) {
        w0 = wi[gg][k], w0.y *= f;
        Cp x = A[j + k], y = w0 * A[i + j + k];
        A[j + k] = x + y, A[i + j + k] = x - y;
      }
    }
    gg++;
  }
  if (f == -1)
    for (int i = 0; i < M; i++) A[i].x /= M;
}
long long n;
int k, b, f[N], g[N], fac[N], inv[N], ans;
void init() {
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i < N; i++) fac[i] = (long long)fac[i - 1] * i % 1000000007;
  for (int i = 2; i < N; i++)
    inv[i] = (long long)(1000000007 - 1000000007 / i) * inv[1000000007 % i] %
             1000000007;
  for (int i = 2; i < N; i++)
    inv[i] = (long long)inv[i] * inv[i - 1] % 1000000007;
  int k = 0;
  for (int i = 2; i <= N; i <<= 1) {
    for (int j = 0; j < i; j++)
      wi[k][j] =
          Cp(cos(j * acos(-1.0) / (i / 2)), sin(j * acos(-1.0) / (i / 2)));
    k++;
  }
}
void FFT_MOD(int *a, int *b, int n) {
  memset(A, 0, sizeof A), memset(B, 0, sizeof B), memset(C, 0, sizeof C),
      memset(D, 0, sizeof D);
  for (int i = 0; i < M; i++) {
    A[i].x = a[i] >> 15;
    B[i].x = a[i] & 32767;
    C[i].x = b[i] >> 15;
    D[i].x = b[i] & 32767;
  }
  FFT(A, 1), FFT(B, 1), FFT(C, 1), FFT(D, 1);
  for (int i = 0; i < M; i++) {
    tmp = A[i] * D[i] + B[i] * C[i];
    A[i] = A[i] * C[i];
    C[i] = B[i] * D[i];
    B[i] = tmp;
  }
  FFT(A, -1), FFT(B, -1), FFT(C, -1), memset(a, 0, sizeof a);
  for (int i = 0; i <= n; i++)
    a[i] =
        ((llround(A[i].x) % 1000000007 << 30) +
         (llround(B[i].x) % 1000000007 << 15) + llround(C[i].x) % 1000000007) %
        1000000007;
}
int c[N];
void work(int *a, int *b, int n, int p) {
  int t = 1;
  memset(c, 0, sizeof c);
  for (int i = 0; i <= n; i++)
    c[i] = (long long)a[i] * t % 1000000007, t = (long long)t * p % 1000000007;
  FFT_MOD(c, b, n);
  memcpy(a, c, sizeof c);
}
int Calc(int n, int m) {
  return (long long)fac[n] * inv[m] % 1000000007 * inv[n - m] % 1000000007;
}
int main() {
  cin >> n >> k;
  if (n > k) return puts("0"), 0;
  for (M = 1; M <= k + k; M <<= 1, l++)
    ;
  for (int i = 0; i < M; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  init(), g[0] = 1, b = 2;
  for (int i = 1; i <= k; i++) f[i] = inv[i];
  while (n) {
    if (n & 1) work(g, f, k, b);
    n >>= 1, work(f, f, k, b), b = (long long)b * b % 1000000007;
  }
  for (int i = n; i <= k; i++)
    (ans += (long long)g[i] * fac[i] % 1000000007 * Calc(k, i) % 1000000007) %=
        1000000007;
  printf("%d\n", ans);
}

### Prompt

Generate 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 INF = 0x7fffffff;
const int N = 1e5 + 5;
struct Cp {
  double x, y;
  Cp(double _x = 0, double _y = 0) { x = _x, y = _y; }
  Cp operator+(const Cp &ch) { return Cp(x + ch.x, y + ch.y); }
  Cp operator-(const Cp &ch) { return Cp(x - ch.x, y - ch.y); }
  Cp operator*(const Cp &ch) {
    return Cp(x * ch.x - y * ch.y, x * ch.y + y * ch.x);
  }
} A[N], B[N], C[N], D[N], w, w0, tmp, wi[16][65536];
;
int M, l, r[N];
void FFT(Cp *A, int f) {
  for (int i = 0; i < M; i++)
    if (r[i] > i) swap(A[r[i]], A[i]);
  int gg = 0;
  for (int i = 1; i < M; i <<= 1) {
    w.x = cos(acos(-1.0) / i), w.y = sin(acos(-1.0) / i) * f;
    for (int j = 0; j < M; j += (i << 1)) {
      for (int k = 0; k < i; k++) {
        w0 = wi[gg][k], w0.y *= f;
        Cp x = A[j + k], y = w0 * A[i + j + k];
        A[j + k] = x + y, A[i + j + k] = x - y;
      }
    }
    gg++;
  }
  if (f == -1)
    for (int i = 0; i < M; i++) A[i].x /= M;
}
long long n;
int k, b, f[N], g[N], fac[N], inv[N], ans;
void init() {
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i < N; i++) fac[i] = (long long)fac[i - 1] * i % 1000000007;
  for (int i = 2; i < N; i++)
    inv[i] = (long long)(1000000007 - 1000000007 / i) * inv[1000000007 % i] %
             1000000007;
  for (int i = 2; i < N; i++)
    inv[i] = (long long)inv[i] * inv[i - 1] % 1000000007;
  int k = 0;
  for (int i = 2; i <= N; i <<= 1) {
    for (int j = 0; j < i; j++)
      wi[k][j] =
          Cp(cos(j * acos(-1.0) / (i / 2)), sin(j * acos(-1.0) / (i / 2)));
    k++;
  }
}
void FFT_MOD(int *a, int *b, int n) {
  memset(A, 0, sizeof A), memset(B, 0, sizeof B), memset(C, 0, sizeof C),
      memset(D, 0, sizeof D);
  for (int i = 0; i < M; i++) {
    A[i].x = a[i] >> 15;
    B[i].x = a[i] & 32767;
    C[i].x = b[i] >> 15;
    D[i].x = b[i] & 32767;
  }
  FFT(A, 1), FFT(B, 1), FFT(C, 1), FFT(D, 1);
  for (int i = 0; i < M; i++) {
    tmp = A[i] * D[i] + B[i] * C[i];
    A[i] = A[i] * C[i];
    C[i] = B[i] * D[i];
    B[i] = tmp;
  }
  FFT(A, -1), FFT(B, -1), FFT(C, -1), memset(a, 0, sizeof a);
  for (int i = 0; i <= n; i++)
    a[i] =
        ((llround(A[i].x) % 1000000007 << 30) +
         (llround(B[i].x) % 1000000007 << 15) + llround(C[i].x) % 1000000007) %
        1000000007;
}
int c[N];
void work(int *a, int *b, int n, int p) {
  int t = 1;
  memset(c, 0, sizeof c);
  for (int i = 0; i <= n; i++)
    c[i] = (long long)a[i] * t % 1000000007, t = (long long)t * p % 1000000007;
  FFT_MOD(c, b, n);
  memcpy(a, c, sizeof c);
}
int Calc(int n, int m) {
  return (long long)fac[n] * inv[m] % 1000000007 * inv[n - m] % 1000000007;
}
int main() {
  cin >> n >> k;
  if (n > k) return puts("0"), 0;
  for (M = 1; M <= k + k; M <<= 1, l++)
    ;
  for (int i = 0; i < M; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  init(), g[0] = 1, b = 2;
  for (int i = 1; i <= k; i++) f[i] = inv[i];
  while (n) {
    if (n & 1) work(g, f, k, b);
    n >>= 1, work(f, f, k, b), b = (long long)b * b % 1000000007;
  }
  for (int i = n; i <= k; i++)
    (ans += (long long)g[i] * fac[i] % 1000000007 * Calc(k, i) % 1000000007) %=
        1000000007;
  printf("%d\n", ans);
}

```