#include <bits/stdc++.h>
using namespace std;
struct E {
  long double x, y;
  E() {}
  E(long double xx, long double yy) {
    x = xx;
    y = yy;
  }
  friend E operator+(E x, E y) {
    x.x += y.x;
    x.y += y.y;
    return x;
  }
  friend E operator-(E x, E y) {
    x.x -= y.x;
    x.y -= y.y;
    return x;
  }
  friend E operator*(E x, E y) {
    E k;
    k.x = x.x * y.x - x.y * y.y;
    k.y = x.x * y.y + x.y * y.x;
    return k;
  }
} A1[70010], B1[70010], A2[70010], B2[70010], C1[70010], C2[70010], C3[70010],
    rtn[140010];
long long A[70010], B[70010];
int id[70010];
double pi = acos(-1);
long long mod = 1000000007;
long long M = sqrt(mod) + 1;
long long jc[30010], ny[30010];
long long f[30010], g[30010];
long long G(long x, int k) {
  if (k == 0) return 1;
  long long y = G(x, k / 2);
  if (k % 2 == 0) return y * y % mod;
  return y * y % mod * x % mod;
}
void fft(E *A, int n, int t) {
  int i, j, k;
  for (i = 0; i < (1 << n); i++)
    if (id[i] < i) swap(A[id[i]], A[i]);
  for (i = 1; i <= n; i++)
    for (j = 0; j < (1 << n); j += (1 << i))
      for (k = j; k < j + (1 << i - 1); k++) {
        E x = A[k], y = rtn[(1 << i) + ((1 << i) + t * (k - j)) % (1 << i)] *
                        A[k + (1 << i - 1)];
        A[k] = x + y;
        A[k + (1 << i - 1)] = x - y;
      }
  if (t == -1)
    for (i = 0; i < (1 << n); i++) A[i].x /= (1 << n), A[i].y /= (1 << n);
}
void mfft(long long *A, long long *B, int n) {
  int i;
  for (i = 0; i < (1 << n); i++) {
    A1[i].x = A[i] / M;
    A2[i].x = A[i] % M;
    B1[i].x = B[i] / M;
    B2[i].x = B[i] % M;
  }
  fft(A1, n, 1);
  fft(A2, n, 1);
  fft(B1, n, 1);
  fft(B2, n, 1);
  for (i = 0; i < (1 << n); i++) {
    C1[i] = A1[i] * B1[i];
    C2[i] = A1[i] * B2[i] + A2[i] * B1[i];
    C3[i] = A2[i] * B2[i];
    A1[i].x = A1[i].y = A2[i].x = A2[i].y = 0;
    B1[i].x = B1[i].y = B2[i].x = B2[i].y = 0;
  }
  fft(C1, n, -1);
  fft(C2, n, -1);
  fft(C3, n, -1);
  for (i = 0; i < (1 << n); i++) {
    long long x = (long long)(C1[i].x + 0.5) % mod * M % mod * M % mod;
    x = (x + (long long)(C2[i].x + 0.5) % mod * M % mod) % mod;
    x = (x + (long long)(C3[i].x + 0.5) % mod) % mod;
    A[i] = x;
    C1[i].x = C1[i].y = C2[i].x = C2[i].y = C3[i].x = C3[i].y = 0;
  }
}
int main() {
  int m, i, j, N, s = 1;
  long long n, ans = 0;
  scanf("%I64d%d", &n, &m);
  if (n > m) {
    printf("0\n");
    return 0;
  }
  ny[1] = 1;
  for (i = 2; i <= m; i++) ny[i] = (mod - mod / i) * ny[mod % i] % mod;
  jc[0] = ny[0] = 1;
  for (i = 1; i <= m; i++) {
    ny[i] = ny[i] * ny[i - 1] % mod;
    jc[i] = jc[i - 1] * i % mod;
  }
  for (N = 0; (1 << N) < m + 1; N++)
    ;
  N++;
  for (i = 1; i < (1 << N); i++)
    id[i] = (id[i >> 1] >> 1) + (1 << N - 1) * (i & 1);
  for (i = 0; i <= N; i++)
    for (j = 0; j < (1 << i); j++)
      rtn[(1 << i) + j] =
          E(cos(j * 2 * pi / (1 << i)), sin(j * 2 * pi / (1 << i)));
  f[0] = 1;
  for (i = 1; i <= m; i++) g[i] = jc[m] * ny[i] % mod * ny[m - i] % mod;
  while (n) {
    if (n & 1) {
      long long x = 1, y = G(2, s);
      for (i = 0; i <= m; i++) {
        A[i] = f[i] * x % mod * jc[m - i] % mod;
        B[i] = g[i] * jc[m - i] % mod;
        x = x * y % mod;
      }
      mfft(A, B, N);
      for (i = 0; i <= m; i++) f[i] = A[i] * ny[m] % mod * ny[m - i] % mod;
      for (i = 0; i < (1 << N); i++) A[i] = B[i] = 0;
    }
    long long x = 1, y = G(2, s);
    for (i = 0; i <= m; i++) {
      A[i] = g[i] * x % mod * jc[m - i] % mod;
      B[i] = g[i] * jc[m - i] % mod;
      x = x * y % mod;
    }
    mfft(A, B, N);
    for (i = 0; i <= m; i++) g[i] = A[i] * ny[m] % mod * ny[m - i] % mod;
    for (i = 0; i < (1 << N); i++) A[i] = B[i] = 0;
    s *= 2;
    n >>= 1;
  }
  for (i = 0; i <= m; i++) ans = (ans + f[i]) % mod;
  printf("%I64d\n", ans);
  return 0;
}

### Prompt

Please provide a cpp coded solution 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;
struct E {
  long double x, y;
  E() {}
  E(long double xx, long double yy) {
    x = xx;
    y = yy;
  }
  friend E operator+(E x, E y) {
    x.x += y.x;
    x.y += y.y;
    return x;
  }
  friend E operator-(E x, E y) {
    x.x -= y.x;
    x.y -= y.y;
    return x;
  }
  friend E operator*(E x, E y) {
    E k;
    k.x = x.x * y.x - x.y * y.y;
    k.y = x.x * y.y + x.y * y.x;
    return k;
  }
} A1[70010], B1[70010], A2[70010], B2[70010], C1[70010], C2[70010], C3[70010],
    rtn[140010];
long long A[70010], B[70010];
int id[70010];
double pi = acos(-1);
long long mod = 1000000007;
long long M = sqrt(mod) + 1;
long long jc[30010], ny[30010];
long long f[30010], g[30010];
long long G(long x, int k) {
  if (k == 0) return 1;
  long long y = G(x, k / 2);
  if (k % 2 == 0) return y * y % mod;
  return y * y % mod * x % mod;
}
void fft(E *A, int n, int t) {
  int i, j, k;
  for (i = 0; i < (1 << n); i++)
    if (id[i] < i) swap(A[id[i]], A[i]);
  for (i = 1; i <= n; i++)
    for (j = 0; j < (1 << n); j += (1 << i))
      for (k = j; k < j + (1 << i - 1); k++) {
        E x = A[k], y = rtn[(1 << i) + ((1 << i) + t * (k - j)) % (1 << i)] *
                        A[k + (1 << i - 1)];
        A[k] = x + y;
        A[k + (1 << i - 1)] = x - y;
      }
  if (t == -1)
    for (i = 0; i < (1 << n); i++) A[i].x /= (1 << n), A[i].y /= (1 << n);
}
void mfft(long long *A, long long *B, int n) {
  int i;
  for (i = 0; i < (1 << n); i++) {
    A1[i].x = A[i] / M;
    A2[i].x = A[i] % M;
    B1[i].x = B[i] / M;
    B2[i].x = B[i] % M;
  }
  fft(A1, n, 1);
  fft(A2, n, 1);
  fft(B1, n, 1);
  fft(B2, n, 1);
  for (i = 0; i < (1 << n); i++) {
    C1[i] = A1[i] * B1[i];
    C2[i] = A1[i] * B2[i] + A2[i] * B1[i];
    C3[i] = A2[i] * B2[i];
    A1[i].x = A1[i].y = A2[i].x = A2[i].y = 0;
    B1[i].x = B1[i].y = B2[i].x = B2[i].y = 0;
  }
  fft(C1, n, -1);
  fft(C2, n, -1);
  fft(C3, n, -1);
  for (i = 0; i < (1 << n); i++) {
    long long x = (long long)(C1[i].x + 0.5) % mod * M % mod * M % mod;
    x = (x + (long long)(C2[i].x + 0.5) % mod * M % mod) % mod;
    x = (x + (long long)(C3[i].x + 0.5) % mod) % mod;
    A[i] = x;
    C1[i].x = C1[i].y = C2[i].x = C2[i].y = C3[i].x = C3[i].y = 0;
  }
}
int main() {
  int m, i, j, N, s = 1;
  long long n, ans = 0;
  scanf("%I64d%d", &n, &m);
  if (n > m) {
    printf("0\n");
    return 0;
  }
  ny[1] = 1;
  for (i = 2; i <= m; i++) ny[i] = (mod - mod / i) * ny[mod % i] % mod;
  jc[0] = ny[0] = 1;
  for (i = 1; i <= m; i++) {
    ny[i] = ny[i] * ny[i - 1] % mod;
    jc[i] = jc[i - 1] * i % mod;
  }
  for (N = 0; (1 << N) < m + 1; N++)
    ;
  N++;
  for (i = 1; i < (1 << N); i++)
    id[i] = (id[i >> 1] >> 1) + (1 << N - 1) * (i & 1);
  for (i = 0; i <= N; i++)
    for (j = 0; j < (1 << i); j++)
      rtn[(1 << i) + j] =
          E(cos(j * 2 * pi / (1 << i)), sin(j * 2 * pi / (1 << i)));
  f[0] = 1;
  for (i = 1; i <= m; i++) g[i] = jc[m] * ny[i] % mod * ny[m - i] % mod;
  while (n) {
    if (n & 1) {
      long long x = 1, y = G(2, s);
      for (i = 0; i <= m; i++) {
        A[i] = f[i] * x % mod * jc[m - i] % mod;
        B[i] = g[i] * jc[m - i] % mod;
        x = x * y % mod;
      }
      mfft(A, B, N);
      for (i = 0; i <= m; i++) f[i] = A[i] * ny[m] % mod * ny[m - i] % mod;
      for (i = 0; i < (1 << N); i++) A[i] = B[i] = 0;
    }
    long long x = 1, y = G(2, s);
    for (i = 0; i <= m; i++) {
      A[i] = g[i] * x % mod * jc[m - i] % mod;
      B[i] = g[i] * jc[m - i] % mod;
      x = x * y % mod;
    }
    mfft(A, B, N);
    for (i = 0; i <= m; i++) g[i] = A[i] * ny[m] % mod * ny[m - i] % mod;
    for (i = 0; i < (1 << N); i++) A[i] = B[i] = 0;
    s *= 2;
    n >>= 1;
  }
  for (i = 0; i <= m; i++) ans = (ans + f[i]) % mod;
  printf("%I64d\n", ans);
  return 0;
}

```