#include <bits/stdc++.h>
using namespace std;
const int mo = 1000000007;
const int P[3] = {1004535809, 998244353, 469762049};
int m, M, U[30005], V[30005], rev[66000], a[3][66000], b[3][66000],
    W[3][2][16][32768], g[66000], f[66000];
long long n, ans;
long long XX(long long x, long long y, long long mo) {
  x %= mo;
  y %= mo;
  return ((x * y - (long long)((long double)x / mo * y) * mo) % mo + mo) % mo;
}
long long po(long long x, int y, long long mo) {
  long long z = 1;
  for (; y; y >>= 1, x = x * x % mo)
    if (y & 1) z = z * x % mo;
  return z;
}
void fft(int a[], int o, int d) {
  for (int i = 0; i < M; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int m = 2, k = 1, I = 0; m <= M; k = m, m <<= 1, ++I)
    for (int i = 0; i < M; i += m)
      for (int j = i; j < i + k; ++j) {
        int u = a[j], v = 1ll * a[j + k] * W[o][d][I][j - i] % P[o];
        a[j] = (u + v) % P[o];
        a[j + k] = (u - v) % P[o];
      }
  if (d) {
    long long x = po(M, P[o] - 2, P[o]);
    for (int i = 0; i < M; ++i) a[i] = x * a[i] % P[o];
  }
}
int CRT(long long x, long long y, long long z) {
  long long p = 1ll * P[0] * P[1],
            s = (XX(x * P[1], po(P[1], P[0] - 2, P[0]), p) +
                 XX(y * P[0], po(P[0], P[1] - 2, P[1]), p)) %
                p;
  return (((z - s % P[2]) * po(p % P[2], P[2] - 2, P[2]) % P[2] + P[2]) % P[2] *
              (p % mo) +
          s % mo) %
         mo;
}
void mul(int f[], int g[], int S) {
  for (int i = 0; i < M; ++i) {
    long long x = po(2, 1ll * i * S % (mo - 1), mo);
    for (int o = 0; o < 3; ++o) a[o][i] = x * f[i] % mo, b[o][i] = g[i];
  }
  for (int o = 0; o < 3; ++o) {
    fft(a[o], o, 0);
    fft(b[o], o, 0);
    for (int i = 0; i < M; ++i) a[o][i] = 1ll * a[o][i] * b[o][i] % P[o];
    fft(a[o], o, 1);
  }
  for (int i = 0; i <= m; ++i) f[i] = CRT(a[0][i], a[1][i], a[2][i]);
}
int main() {
  scanf("%lld%d", &n, &m);
  if (n > m) {
    puts("0");
    return 0;
  }
  for (M = 1; M <= m + m; M <<= 1)
    ;
  for (int i = 0; i < M; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) * (M >> 1);
  for (int o = 0; o < 3; ++o) {
    for (int I = 0, m = 2, k = 1; m <= M; ++I, k = m, m <<= 1) {
      long long x = po(3, (P[o] - 1) / m, P[o]), y = 1;
      for (int i = 0; i < k; ++i) W[o][0][I][i] = y, y = y * x % P[o];
    }
    for (int I = 0, m = 2, k = 1; m <= M; ++I, k = m, m <<= 1) {
      long long x = po(3, (1 - P[o]) / m % (P[o] - 1) + P[o] - 1, P[o]), y = 1;
      for (int i = 0; i < k; ++i) W[o][1][I][i] = y, y = y * x % P[o];
    }
  }
  U[0] = 1;
  for (int i = 1; i <= m; ++i) U[i] = 1ll * U[i - 1] * i % mo;
  V[m] = po(U[m], mo - 2, mo);
  for (int i = m - 1; ~i; --i) V[i] = 1ll * V[i + 1] * (i + 1) % mo;
  g[0] = 1;
  for (int i = 1; i <= m; ++i) f[i] = V[i];
  for (int S = 1; S <= n; S <<= 1) {
    if (n & S) mul(g, f, S);
    mul(f, f, S);
  }
  for (int i = n; i <= m; ++i)
    (ans += 1ll * g[i] * U[m] % mo * V[m - i] % mo) %= mo;
  printf("%lld\n", (ans + mo) % mo);
  return 0;
}

### 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 mo = 1000000007;
const int P[3] = {1004535809, 998244353, 469762049};
int m, M, U[30005], V[30005], rev[66000], a[3][66000], b[3][66000],
    W[3][2][16][32768], g[66000], f[66000];
long long n, ans;
long long XX(long long x, long long y, long long mo) {
  x %= mo;
  y %= mo;
  return ((x * y - (long long)((long double)x / mo * y) * mo) % mo + mo) % mo;
}
long long po(long long x, int y, long long mo) {
  long long z = 1;
  for (; y; y >>= 1, x = x * x % mo)
    if (y & 1) z = z * x % mo;
  return z;
}
void fft(int a[], int o, int d) {
  for (int i = 0; i < M; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int m = 2, k = 1, I = 0; m <= M; k = m, m <<= 1, ++I)
    for (int i = 0; i < M; i += m)
      for (int j = i; j < i + k; ++j) {
        int u = a[j], v = 1ll * a[j + k] * W[o][d][I][j - i] % P[o];
        a[j] = (u + v) % P[o];
        a[j + k] = (u - v) % P[o];
      }
  if (d) {
    long long x = po(M, P[o] - 2, P[o]);
    for (int i = 0; i < M; ++i) a[i] = x * a[i] % P[o];
  }
}
int CRT(long long x, long long y, long long z) {
  long long p = 1ll * P[0] * P[1],
            s = (XX(x * P[1], po(P[1], P[0] - 2, P[0]), p) +
                 XX(y * P[0], po(P[0], P[1] - 2, P[1]), p)) %
                p;
  return (((z - s % P[2]) * po(p % P[2], P[2] - 2, P[2]) % P[2] + P[2]) % P[2] *
              (p % mo) +
          s % mo) %
         mo;
}
void mul(int f[], int g[], int S) {
  for (int i = 0; i < M; ++i) {
    long long x = po(2, 1ll * i * S % (mo - 1), mo);
    for (int o = 0; o < 3; ++o) a[o][i] = x * f[i] % mo, b[o][i] = g[i];
  }
  for (int o = 0; o < 3; ++o) {
    fft(a[o], o, 0);
    fft(b[o], o, 0);
    for (int i = 0; i < M; ++i) a[o][i] = 1ll * a[o][i] * b[o][i] % P[o];
    fft(a[o], o, 1);
  }
  for (int i = 0; i <= m; ++i) f[i] = CRT(a[0][i], a[1][i], a[2][i]);
}
int main() {
  scanf("%lld%d", &n, &m);
  if (n > m) {
    puts("0");
    return 0;
  }
  for (M = 1; M <= m + m; M <<= 1)
    ;
  for (int i = 0; i < M; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) * (M >> 1);
  for (int o = 0; o < 3; ++o) {
    for (int I = 0, m = 2, k = 1; m <= M; ++I, k = m, m <<= 1) {
      long long x = po(3, (P[o] - 1) / m, P[o]), y = 1;
      for (int i = 0; i < k; ++i) W[o][0][I][i] = y, y = y * x % P[o];
    }
    for (int I = 0, m = 2, k = 1; m <= M; ++I, k = m, m <<= 1) {
      long long x = po(3, (1 - P[o]) / m % (P[o] - 1) + P[o] - 1, P[o]), y = 1;
      for (int i = 0; i < k; ++i) W[o][1][I][i] = y, y = y * x % P[o];
    }
  }
  U[0] = 1;
  for (int i = 1; i <= m; ++i) U[i] = 1ll * U[i - 1] * i % mo;
  V[m] = po(U[m], mo - 2, mo);
  for (int i = m - 1; ~i; --i) V[i] = 1ll * V[i + 1] * (i + 1) % mo;
  g[0] = 1;
  for (int i = 1; i <= m; ++i) f[i] = V[i];
  for (int S = 1; S <= n; S <<= 1) {
    if (n & S) mul(g, f, S);
    mul(f, f, S);
  }
  for (int i = n; i <= m; ++i)
    (ans += 1ll * g[i] * U[m] % mo * V[m - i] % mo) %= mo;
  printf("%lld\n", (ans + mo) % mo);
  return 0;
}

```