#include <bits/stdc++.h>
const int N = 65540;
const int mod = 1e9 + 7;
long long n;
int m, fac[N], inv[N];
int F[N], G[N], rnk[N], Ans;
int ksm(int u, int v, int md) {
  int res = 1;
  for (; v; v >>= 1, u = 1ll * u * u % md)
    if (v & 1) res = 1ll * res * u % md;
  return res;
}
inline void swap(int &u, int &v) {
  int o = u;
  u = v;
  v = o;
}
struct Mtt {
  int f[3][N], g[3][N], len, Mod[3] = {7 << 26 | 1, 998244353, 479 << 21 | 1};
  int p01 = ksm(Mod[0], Mod[1] - 2, Mod[1]);
  int p012 = ksm(1ll * Mod[0] * Mod[1] % Mod[2], Mod[2] - 2, Mod[2]);
  void init(int *a, int *b, int c) {
    for (int i = 0; i < 3; i++) {
      int C = ksm(2, c, mod);
      for (int j = 0, k = 1; j <= m; j++, k = 1ll * k * C % mod)
        f[i][j] = 1ll * a[j] * k % mod;
      for (int j = m + 1; j < len; j++) f[i][j] = 0;
      for (int j = 0; j <= m; j++) g[i][j] = b[j];
      for (int j = m + 1; j < len; j++) g[i][j] = 0;
    }
  }
  void ntt(int *t, int op, int opt) {
    int g = 3, g_ = ksm(g, Mod[op] - 2, Mod[op]);
    for (int i = 0; i < len; i++)
      if (i < rnk[i]) swap(t[i], t[rnk[i]]);
    for (int i = 1; i < len; i <<= 1) {
      int wn = ksm(~opt ? g : g_, (Mod[op] - 1) / (i << 1), Mod[op]);
      for (int j = 0, J = i << 1; j < len; j += J) {
        int w = 1;
        for (int k = j; k < i + j; k++, w = 1ll * w * wn % Mod[op]) {
          int r = 1ll * t[i + k] * w % Mod[op];
          t[i + k] = (t[k] - r + Mod[op]) % Mod[op];
          t[k] = (t[k] + r) % Mod[op];
        }
      }
    }
    if (~opt) return;
    int ny = ksm(len, Mod[op] - 2, Mod[op]);
    for (int i = 0; i < len; i++) t[i] = 1ll * t[i] * ny % Mod[op];
  }
  void doit(int *a) {
    for (int i = 0; i < 3; i++) ntt(f[i], i, 1);
    for (int i = 0; i < 3; i++) ntt(g[i], i, 1);
    for (int i = 0; i < 3; i++)
      for (int j = 0; j < len; j++) f[i][j] = 1ll * f[i][j] * g[i][j] % Mod[i];
    for (int i = 0; i < 3; i++) ntt(f[i], i, -1);
    for (int i = 0; i <= m; i++) {
      long long j =
          1ll * (f[1][i] - f[0][i] + Mod[1]) * p01 % Mod[1] * Mod[0] + f[0][i];
      a[i] = (1ll * (f[2][i] - j % Mod[2] + Mod[2]) * p012 % Mod[2] * Mod[0] %
                  mod * Mod[1] % mod +
              j % mod) %
             mod;
    }
  }
} MTT;
void mul(int *a, int *b, int c) {
  MTT.init(a, b, c);
  MTT.doit(a);
}
int main() {
  scanf("%lld%d", &n, &m);
  if (n > m) {
    puts("0");
    return 0;
  }
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i <= m; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[m] = ksm(fac[m], mod - 2, mod);
  for (int i = m - 1; i >= 2; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
  for (int i = 1; i <= m; i++) F[i] = inv[i];
  G[0] = 1;
  int len = 1, _2 = -1;
  while (len < m + m + 2) len <<= 1, _2++;
  MTT.len = len;
  for (int i = 0; i < len; i++) rnk[i] = (rnk[i >> 1] >> 1) | ((i & 1) << _2);
  for (int i = 1; n; n >>= 1, mul(F, F, i), i <<= 1)
    if (n & 1) mul(G, F, i);
  for (int i = 0; i <= m; i++)
    Ans = (Ans + 1ll * G[i] * fac[i] % mod * fac[m] % mod * inv[i] % mod *
                     inv[m - i] % mod) %
          mod;
  printf("%d\n", Ans);
}

### Prompt

Please create a solution in cpp 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>
const int N = 65540;
const int mod = 1e9 + 7;
long long n;
int m, fac[N], inv[N];
int F[N], G[N], rnk[N], Ans;
int ksm(int u, int v, int md) {
  int res = 1;
  for (; v; v >>= 1, u = 1ll * u * u % md)
    if (v & 1) res = 1ll * res * u % md;
  return res;
}
inline void swap(int &u, int &v) {
  int o = u;
  u = v;
  v = o;
}
struct Mtt {
  int f[3][N], g[3][N], len, Mod[3] = {7 << 26 | 1, 998244353, 479 << 21 | 1};
  int p01 = ksm(Mod[0], Mod[1] - 2, Mod[1]);
  int p012 = ksm(1ll * Mod[0] * Mod[1] % Mod[2], Mod[2] - 2, Mod[2]);
  void init(int *a, int *b, int c) {
    for (int i = 0; i < 3; i++) {
      int C = ksm(2, c, mod);
      for (int j = 0, k = 1; j <= m; j++, k = 1ll * k * C % mod)
        f[i][j] = 1ll * a[j] * k % mod;
      for (int j = m + 1; j < len; j++) f[i][j] = 0;
      for (int j = 0; j <= m; j++) g[i][j] = b[j];
      for (int j = m + 1; j < len; j++) g[i][j] = 0;
    }
  }
  void ntt(int *t, int op, int opt) {
    int g = 3, g_ = ksm(g, Mod[op] - 2, Mod[op]);
    for (int i = 0; i < len; i++)
      if (i < rnk[i]) swap(t[i], t[rnk[i]]);
    for (int i = 1; i < len; i <<= 1) {
      int wn = ksm(~opt ? g : g_, (Mod[op] - 1) / (i << 1), Mod[op]);
      for (int j = 0, J = i << 1; j < len; j += J) {
        int w = 1;
        for (int k = j; k < i + j; k++, w = 1ll * w * wn % Mod[op]) {
          int r = 1ll * t[i + k] * w % Mod[op];
          t[i + k] = (t[k] - r + Mod[op]) % Mod[op];
          t[k] = (t[k] + r) % Mod[op];
        }
      }
    }
    if (~opt) return;
    int ny = ksm(len, Mod[op] - 2, Mod[op]);
    for (int i = 0; i < len; i++) t[i] = 1ll * t[i] * ny % Mod[op];
  }
  void doit(int *a) {
    for (int i = 0; i < 3; i++) ntt(f[i], i, 1);
    for (int i = 0; i < 3; i++) ntt(g[i], i, 1);
    for (int i = 0; i < 3; i++)
      for (int j = 0; j < len; j++) f[i][j] = 1ll * f[i][j] * g[i][j] % Mod[i];
    for (int i = 0; i < 3; i++) ntt(f[i], i, -1);
    for (int i = 0; i <= m; i++) {
      long long j =
          1ll * (f[1][i] - f[0][i] + Mod[1]) * p01 % Mod[1] * Mod[0] + f[0][i];
      a[i] = (1ll * (f[2][i] - j % Mod[2] + Mod[2]) * p012 % Mod[2] * Mod[0] %
                  mod * Mod[1] % mod +
              j % mod) %
             mod;
    }
  }
} MTT;
void mul(int *a, int *b, int c) {
  MTT.init(a, b, c);
  MTT.doit(a);
}
int main() {
  scanf("%lld%d", &n, &m);
  if (n > m) {
    puts("0");
    return 0;
  }
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i <= m; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[m] = ksm(fac[m], mod - 2, mod);
  for (int i = m - 1; i >= 2; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
  for (int i = 1; i <= m; i++) F[i] = inv[i];
  G[0] = 1;
  int len = 1, _2 = -1;
  while (len < m + m + 2) len <<= 1, _2++;
  MTT.len = len;
  for (int i = 0; i < len; i++) rnk[i] = (rnk[i >> 1] >> 1) | ((i & 1) << _2);
  for (int i = 1; n; n >>= 1, mul(F, F, i), i <<= 1)
    if (n & 1) mul(G, F, i);
  for (int i = 0; i <= m; i++)
    Ans = (Ans + 1ll * G[i] * fac[i] % mod * fac[m] % mod * inv[i] % mod *
                     inv[m - i] % mod) %
          mod;
  printf("%d\n", Ans);
}

```