#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const double PI = acos(-1);
long long qpow(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
struct Complex {
  double x, y;
  Complex(double a = 0, double b = 0) : x(a), y(b) {}
  Complex operator+(const Complex &rhs) {
    return Complex(x + rhs.x, y + rhs.y);
  }
  Complex operator-(const Complex &rhs) {
    return Complex(x - rhs.x, y - rhs.y);
  }
  Complex operator*(const Complex &rhs) {
    return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  }
  Complex conj() { return Complex(x, -y); }
} w[N];
const long long mod = 1e9 + 7;
int tr[N];
int getLen(int n) {
  int len = 1;
  while (len < (n << 1)) len <<= 1;
  for (int i = 0; i < len; i++)
    tr[i] = (tr[i >> 1] >> 1) | (i & 1 ? len >> 1 : 0);
  for (int i = 0; i < len; i++)
    w[i] = w[i] = Complex(cos(2 * PI * i / len), sin(2 * PI * i / len));
  return len;
}
void FFT(Complex *A, int len) {
  for (int i = 0; i < len; i++)
    if (i < tr[i]) swap(A[i], A[tr[i]]);
  for (int i = 2, lyc = len >> 1; i <= len; i <<= 1, lyc >>= 1)
    for (int j = 0; j < len; j += i) {
      Complex *l = A + j, *r = A + j + (i >> 1), *p = w;
      for (int k = 0; k < i >> 1; k++) {
        Complex tmp = *r * *p;
        *r = *l - tmp, *l = *l + tmp;
        ++l, ++r, p += lyc;
      }
    }
}
void MTT(long long *x, long long *y, long long *z, int len) {
  for (int i = 0; i < len; i++) (x[i] += mod) %= mod, (y[i] += mod) %= mod;
  static Complex a[N], b[N];
  static Complex dfta[N], dftb[N], dftc[N], dftd[N];
  for (int i = 0; i < len; i++) a[i] = Complex(x[i] & 32767, x[i] >> 15);
  for (int i = 0; i < len; i++) b[i] = Complex(y[i] & 32767, y[i] >> 15);
  FFT(a, len), FFT(b, len);
  for (int i = 0; i < len; i++) {
    int j = (len - i) & (len - 1);
    static Complex da, db, dc, dd;
    da = (a[i] + a[j].conj()) * Complex(0.5, 0);
    db = (a[i] - a[j].conj()) * Complex(0, -0.5);
    dc = (b[i] + b[j].conj()) * Complex(0.5, 0);
    dd = (b[i] - b[j].conj()) * Complex(0, -0.5);
    dfta[j] = da * dc;
    dftb[j] = da * dd;
    dftc[j] = db * dc;
    dftd[j] = db * dd;
  }
  for (int i = 0; i < len; i++) a[i] = dfta[i] + dftb[i] * Complex(0, 1);
  for (int i = 0; i < len; i++) b[i] = dftc[i] + dftd[i] * Complex(0, 1);
  FFT(a, len), FFT(b, len);
  for (int i = 0; i < len; i++) {
    long long da = (long long)(a[i].x / len + 0.5) % mod;
    long long db = (long long)(a[i].y / len + 0.5) % mod;
    long long dc = (long long)(b[i].x / len + 0.5) % mod;
    long long dd = (long long)(b[i].y / len + 0.5) % mod;
    z[i] = (da + ((long long)(db + dc) << 15) + ((long long)dd << 30)) % mod;
  }
}
long long fac[N], ifac[N];
void init(int siz) {
  fac[0] = 1;
  for (int i = 1; i <= siz; i++) fac[i] = i * fac[i - 1] % mod;
  ifac[siz] = qpow(fac[siz], mod - 2, mod);
  for (int i = siz; i >= 1; i--) ifac[i - 1] = ifac[i] * i % mod;
}
long long C(long long n, long long m) {
  if (m == 0 || n == m) return 1;
  if (m > n) return 0;
  if (m == 1) return n;
  return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
void mul(long long *x, long long *y, long long *z, int n, long long now) {
  static long long a[N], b[N];
  for (int i = 0; i < n; i++)
    a[i] = x[i] * qpow(2ll, now * i % (mod - 1), mod) % mod, b[i] = y[i];
  int len = getLen(n);
  MTT(a, b, z, len);
  for (int i = 0; i < len; i++) a[i] = b[i] = 0;
}
long long base[N], f[N];
int main() {
  long long n, k;
  scanf("%lld%lld", &k, &n);
  if (k > n)
    printf("0\n");
  else {
    n++;
    init(n);
    for (int i = 1; i < n; i++) base[i] = ifac[i];
    f[0] = 1;
    for (int bit = 0, now = 0; (1 << bit) <= k; bit++) {
      if ((1 << bit) & k) mul(base, f, f, n, now), now |= 1 << bit;
      mul(base, base, base, n, 1 << bit);
    }
    long long ans = 0;
    for (int i = 1; i < n; i++)
      ans = (ans + f[i] * fac[i] % mod * C(n - 1, i) % mod) % mod;
    printf("%lld\n", ans);
  }
  return 0;
}

### Prompt

Please formulate 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 N = 5e5 + 10;
const double PI = acos(-1);
long long qpow(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
struct Complex {
  double x, y;
  Complex(double a = 0, double b = 0) : x(a), y(b) {}
  Complex operator+(const Complex &rhs) {
    return Complex(x + rhs.x, y + rhs.y);
  }
  Complex operator-(const Complex &rhs) {
    return Complex(x - rhs.x, y - rhs.y);
  }
  Complex operator*(const Complex &rhs) {
    return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  }
  Complex conj() { return Complex(x, -y); }
} w[N];
const long long mod = 1e9 + 7;
int tr[N];
int getLen(int n) {
  int len = 1;
  while (len < (n << 1)) len <<= 1;
  for (int i = 0; i < len; i++)
    tr[i] = (tr[i >> 1] >> 1) | (i & 1 ? len >> 1 : 0);
  for (int i = 0; i < len; i++)
    w[i] = w[i] = Complex(cos(2 * PI * i / len), sin(2 * PI * i / len));
  return len;
}
void FFT(Complex *A, int len) {
  for (int i = 0; i < len; i++)
    if (i < tr[i]) swap(A[i], A[tr[i]]);
  for (int i = 2, lyc = len >> 1; i <= len; i <<= 1, lyc >>= 1)
    for (int j = 0; j < len; j += i) {
      Complex *l = A + j, *r = A + j + (i >> 1), *p = w;
      for (int k = 0; k < i >> 1; k++) {
        Complex tmp = *r * *p;
        *r = *l - tmp, *l = *l + tmp;
        ++l, ++r, p += lyc;
      }
    }
}
void MTT(long long *x, long long *y, long long *z, int len) {
  for (int i = 0; i < len; i++) (x[i] += mod) %= mod, (y[i] += mod) %= mod;
  static Complex a[N], b[N];
  static Complex dfta[N], dftb[N], dftc[N], dftd[N];
  for (int i = 0; i < len; i++) a[i] = Complex(x[i] & 32767, x[i] >> 15);
  for (int i = 0; i < len; i++) b[i] = Complex(y[i] & 32767, y[i] >> 15);
  FFT(a, len), FFT(b, len);
  for (int i = 0; i < len; i++) {
    int j = (len - i) & (len - 1);
    static Complex da, db, dc, dd;
    da = (a[i] + a[j].conj()) * Complex(0.5, 0);
    db = (a[i] - a[j].conj()) * Complex(0, -0.5);
    dc = (b[i] + b[j].conj()) * Complex(0.5, 0);
    dd = (b[i] - b[j].conj()) * Complex(0, -0.5);
    dfta[j] = da * dc;
    dftb[j] = da * dd;
    dftc[j] = db * dc;
    dftd[j] = db * dd;
  }
  for (int i = 0; i < len; i++) a[i] = dfta[i] + dftb[i] * Complex(0, 1);
  for (int i = 0; i < len; i++) b[i] = dftc[i] + dftd[i] * Complex(0, 1);
  FFT(a, len), FFT(b, len);
  for (int i = 0; i < len; i++) {
    long long da = (long long)(a[i].x / len + 0.5) % mod;
    long long db = (long long)(a[i].y / len + 0.5) % mod;
    long long dc = (long long)(b[i].x / len + 0.5) % mod;
    long long dd = (long long)(b[i].y / len + 0.5) % mod;
    z[i] = (da + ((long long)(db + dc) << 15) + ((long long)dd << 30)) % mod;
  }
}
long long fac[N], ifac[N];
void init(int siz) {
  fac[0] = 1;
  for (int i = 1; i <= siz; i++) fac[i] = i * fac[i - 1] % mod;
  ifac[siz] = qpow(fac[siz], mod - 2, mod);
  for (int i = siz; i >= 1; i--) ifac[i - 1] = ifac[i] * i % mod;
}
long long C(long long n, long long m) {
  if (m == 0 || n == m) return 1;
  if (m > n) return 0;
  if (m == 1) return n;
  return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
void mul(long long *x, long long *y, long long *z, int n, long long now) {
  static long long a[N], b[N];
  for (int i = 0; i < n; i++)
    a[i] = x[i] * qpow(2ll, now * i % (mod - 1), mod) % mod, b[i] = y[i];
  int len = getLen(n);
  MTT(a, b, z, len);
  for (int i = 0; i < len; i++) a[i] = b[i] = 0;
}
long long base[N], f[N];
int main() {
  long long n, k;
  scanf("%lld%lld", &k, &n);
  if (k > n)
    printf("0\n");
  else {
    n++;
    init(n);
    for (int i = 1; i < n; i++) base[i] = ifac[i];
    f[0] = 1;
    for (int bit = 0, now = 0; (1 << bit) <= k; bit++) {
      if ((1 << bit) & k) mul(base, f, f, n, now), now |= 1 << bit;
      mul(base, base, base, n, 1 << bit);
    }
    long long ans = 0;
    for (int i = 1; i < n; i++)
      ans = (ans + f[i] * fac[i] % mod * C(n - 1, i) % mod) % mod;
    printf("%lld\n", ans);
  }
  return 0;
}

```