#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17 | 5;
long long mod = 1e9 + 7;
long double pi = acos(-1);
struct cp {
  long double a, b;
  cp() { a = b = 0; }
  cp(long double _a, long double _b) { a = _a, b = _b; }
  cp operator+(cp x) const { return cp(a + x.a, b + x.b); }
  cp operator-(cp x) const { return cp(a - x.a, b - x.b); }
  cp operator*(cp x) const { return cp(a * x.a - b * x.b, b * x.a + a * x.b); }
  cp Conj() { return cp(a, -b); }
};
cp p[N], q[N], a[N], b[N], c[N], d[N], kx, bx, ky, by, u, t;
int ret[N], m;
long long x[N], y[N], f[N], g[N], sum[N], inv[N], T[N], len, lg, Ans, two, Two,
    n;
long long Cc(int i, int j) { return sum[j] * inv[j - i] % mod * inv[i] % mod; }
long long sqr(long long a) { return a * a % mod; }
long long power(int x, int y) {
  if (y == 0) return 1;
  if (y % 2)
    return sqr(power(x, y / 2)) * x % mod;
  else
    return sqr(power(x, y / 2));
}
void FFT(cp *a, int n, int opt) {
  for (int i = 1; i <= n; i++)
    if (i < ret[i]) swap(a[i], a[ret[i]]);
  for (int m = 1; m < n; m <<= 1) {
    cp omega(cos(pi / m), opt * sin(pi / m));
    for (int k = 0; k < n; k += m * 2) {
      cp now(1, 0);
      for (int j = 0; j < m; j++) {
        u = a[k + j], t = now * a[k + j + m];
        a[k + j] = u + t;
        a[k + j + m] = u - t;
        now = now * omega;
      }
    }
  }
}
void mul(long long *x, long long *y, int n, long long *ans) {
  cp r(0.5, 0), h(0, -0.5), o(0, 1);
  memset(p, 0, sizeof(p));
  memset(q, 0, sizeof(q));
  for (int i = 0; i <= m; i++) {
    p[i] = cp(x[i] >> 15, x[i] & 32767);
    q[i] = cp(y[i] >> 15, y[i] & 32767);
  }
  FFT(p, n, 1);
  FFT(q, n, 1);
  for (int i = 0; i < n; i++) {
    int j = (n - i) & (n - 1);
    kx = cp(p[i] + p[j].Conj()) * r;
    bx = cp(p[i] - p[j].Conj()) * h;
    ky = cp(q[i] + q[j].Conj()) * r;
    by = cp(q[i] - q[j].Conj()) * h;
    a[i] = kx * ky;
    b[i] = kx * by;
    c[i] = bx * ky;
    d[i] = bx * by;
  }
  for (int i = 0; i < n; i++) {
    p[i] = a[i] + (b[i] + c[i]) * o;
    q[i] = d[i];
  }
  FFT(p, n, -1);
  FFT(q, n, -1);
  for (int i = 0; i <= m; i++) {
    long long a, b, c;
    a = (long long)(p[i].a / n + 0.5) % mod;
    b = (long long)(p[i].b / n + 0.5) % mod;
    c = (long long)(q[i].a / n + 0.5) % mod;
    ans[i] = ((a << 30) % mod + (b << 15) % mod + c) % mod;
  }
}
void work(long long *x, long long *y, int n, long long two) {
  Two = 1;
  memset(T, 0, sizeof(T));
  for (int i = 0; i <= n; i++) {
    T[i] = (x[i] * Two) % mod;
    Two = Two * two % mod;
  }
  mul(T, y, len, T);
  memcpy(x, T, sizeof(T));
}
int main() {
  scanf("%lld%d", &n, &m);
  if (n > m) {
    puts("0");
    return 0;
  }
  sum[0] = 1;
  for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] * i % mod;
  inv[m] = power(sum[m], mod - 2);
  for (int i = m; i >= 1; i--) inv[i - 1] = inv[i] * i % mod;
  for (len = 1; len <= m + m; len <<= 1) lg++;
  for (int i = 1; i <= m; i++) g[i] = inv[i];
  for (int i = 0; i < len; i++)
    ret[i] = (ret[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  f[0] = 1;
  two = 2;
  while (n) {
    if (n & 1) work(f, g, m, two);
    work(g, g, m, two);
    n >>= 1;
    two = sqr(two);
  }
  for (int i = n; i <= m; i++)
    Ans = (Ans + Cc(i, m) * f[i] % mod * sum[i] % mod) % mod;
  printf("%lld", (Ans + mod) % mod);
  return 0;
}

### Prompt

Develop a solution in Cpp 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;
const int N = 1 << 17 | 5;
long long mod = 1e9 + 7;
long double pi = acos(-1);
struct cp {
  long double a, b;
  cp() { a = b = 0; }
  cp(long double _a, long double _b) { a = _a, b = _b; }
  cp operator+(cp x) const { return cp(a + x.a, b + x.b); }
  cp operator-(cp x) const { return cp(a - x.a, b - x.b); }
  cp operator*(cp x) const { return cp(a * x.a - b * x.b, b * x.a + a * x.b); }
  cp Conj() { return cp(a, -b); }
};
cp p[N], q[N], a[N], b[N], c[N], d[N], kx, bx, ky, by, u, t;
int ret[N], m;
long long x[N], y[N], f[N], g[N], sum[N], inv[N], T[N], len, lg, Ans, two, Two,
    n;
long long Cc(int i, int j) { return sum[j] * inv[j - i] % mod * inv[i] % mod; }
long long sqr(long long a) { return a * a % mod; }
long long power(int x, int y) {
  if (y == 0) return 1;
  if (y % 2)
    return sqr(power(x, y / 2)) * x % mod;
  else
    return sqr(power(x, y / 2));
}
void FFT(cp *a, int n, int opt) {
  for (int i = 1; i <= n; i++)
    if (i < ret[i]) swap(a[i], a[ret[i]]);
  for (int m = 1; m < n; m <<= 1) {
    cp omega(cos(pi / m), opt * sin(pi / m));
    for (int k = 0; k < n; k += m * 2) {
      cp now(1, 0);
      for (int j = 0; j < m; j++) {
        u = a[k + j], t = now * a[k + j + m];
        a[k + j] = u + t;
        a[k + j + m] = u - t;
        now = now * omega;
      }
    }
  }
}
void mul(long long *x, long long *y, int n, long long *ans) {
  cp r(0.5, 0), h(0, -0.5), o(0, 1);
  memset(p, 0, sizeof(p));
  memset(q, 0, sizeof(q));
  for (int i = 0; i <= m; i++) {
    p[i] = cp(x[i] >> 15, x[i] & 32767);
    q[i] = cp(y[i] >> 15, y[i] & 32767);
  }
  FFT(p, n, 1);
  FFT(q, n, 1);
  for (int i = 0; i < n; i++) {
    int j = (n - i) & (n - 1);
    kx = cp(p[i] + p[j].Conj()) * r;
    bx = cp(p[i] - p[j].Conj()) * h;
    ky = cp(q[i] + q[j].Conj()) * r;
    by = cp(q[i] - q[j].Conj()) * h;
    a[i] = kx * ky;
    b[i] = kx * by;
    c[i] = bx * ky;
    d[i] = bx * by;
  }
  for (int i = 0; i < n; i++) {
    p[i] = a[i] + (b[i] + c[i]) * o;
    q[i] = d[i];
  }
  FFT(p, n, -1);
  FFT(q, n, -1);
  for (int i = 0; i <= m; i++) {
    long long a, b, c;
    a = (long long)(p[i].a / n + 0.5) % mod;
    b = (long long)(p[i].b / n + 0.5) % mod;
    c = (long long)(q[i].a / n + 0.5) % mod;
    ans[i] = ((a << 30) % mod + (b << 15) % mod + c) % mod;
  }
}
void work(long long *x, long long *y, int n, long long two) {
  Two = 1;
  memset(T, 0, sizeof(T));
  for (int i = 0; i <= n; i++) {
    T[i] = (x[i] * Two) % mod;
    Two = Two * two % mod;
  }
  mul(T, y, len, T);
  memcpy(x, T, sizeof(T));
}
int main() {
  scanf("%lld%d", &n, &m);
  if (n > m) {
    puts("0");
    return 0;
  }
  sum[0] = 1;
  for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] * i % mod;
  inv[m] = power(sum[m], mod - 2);
  for (int i = m; i >= 1; i--) inv[i - 1] = inv[i] * i % mod;
  for (len = 1; len <= m + m; len <<= 1) lg++;
  for (int i = 1; i <= m; i++) g[i] = inv[i];
  for (int i = 0; i < len; i++)
    ret[i] = (ret[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  f[0] = 1;
  two = 2;
  while (n) {
    if (n & 1) work(f, g, m, two);
    work(g, g, m, two);
    n >>= 1;
    two = sqr(two);
  }
  for (int i = n; i <= m; i++)
    Ans = (Ans + Cc(i, m) * f[i] % mod * sum[i] % mod) % mod;
  printf("%lld", (Ans + mod) % mod);
  return 0;
}

```