#include <bits/stdc++.h>
const int N = 1 << 16, MOD = 1000000007;
struct Complex {
  double x, y;
  Complex(double _x = 0., double _y = 0.) : x(_x), y(_y) {}
  inline Complex conj() { return Complex(x, -y); }
};
inline Complex operator+(const Complex &lhs, const Complex &rhs) {
  return Complex(lhs.x + rhs.x, lhs.y + rhs.y);
}
inline Complex operator-(const Complex &lhs, const Complex &rhs) {
  return Complex(lhs.x - rhs.x, lhs.y - rhs.y);
}
inline Complex operator*(const Complex &lhs, const Complex &rhs) {
  return Complex(lhs.x * rhs.x - lhs.y * rhs.y, lhs.x * rhs.y + lhs.y * rhs.x);
}
const Complex I(0., 1.);
int len;
Complex w[N + 1];
void fft(Complex a[]) {
  for (register int i = 0, j = 0; i < len; ++i) {
    if (j < i) std::swap(a[i], a[j]);
    for (register int k = len >> 1; (j ^= k) < k;) k >>= 1;
  }
  for (int m = 2; m <= len; m *= 2) {
    int gap = m / 2, step = N / m;
    for (int i = 0; i < len; i += m) {
      Complex *o = w, *p = &a[i], *q = &a[i + gap];
      for (int j = gap; j--; ++p, ++q, o += step) {
        Complex u = *p, v = *o * *q;
        *p = u + v;
        *q = u - v;
      }
    }
  }
}
inline int power(int base, int exp) {
  int res = 1;
  for (; exp; exp >>= 1) {
    if (exp & 1) res = (long long)res * base % MOD;
    base = (long long)base * base % MOD;
  }
  return res;
}
long long n;
int k;
inline void convolution(int lhs[], const int rhs[]) {
  Complex a[N], b[N];
  for (int i = 0; i < len; ++i) a[i] = Complex(lhs[i] & 32767, lhs[i] >> 15);
  for (int i = 0; i < len; ++i) b[i] = Complex(rhs[i] & 32767, rhs[i] >> 15);
  fft(a);
  fft(b);
  static Complex res[4][N];
  for (int i = 0; i < len; ++i) {
    int j = (len - i) & (len - 1);
    Complex aLo = (a[i] + a[j].conj()) * Complex(.5, 0);
    Complex aHi = (a[i] - a[j].conj()) * Complex(0, -.5);
    Complex bLo = (b[i] + b[j].conj()) * Complex(.5, 0);
    Complex bHi = (b[i] - b[j].conj()) * Complex(0, -.5);
    res[0][i] = aLo * bLo;
    res[1][i] = aLo * bHi;
    res[2][i] = aHi * bLo;
    res[3][i] = aHi * bHi;
  }
  for (int i = 0; i < len; ++i) a[i] = res[0][i] + I * res[1][i];
  for (int i = 0; i < len; ++i) b[i] = res[2][i] + I * res[3][i];
  std::reverse(a + 1, a + len);
  std::reverse(b + 1, b + len);
  fft(a);
  fft(b);
  for (int i = 0; i <= k; ++i) {
    int lo = (long long)(a[i].x / len + .5) % MOD;
    int mid =
        ((long long)(a[i].y / len + .5) + (long long)(b[i].x / len + .5)) % MOD;
    int hi = (long long)(b[i].y / len + .5) % MOD;
    lhs[i] = (lo + ((long long)mid << 15) + ((long long)hi << 30)) % MOD;
  }
  for (int i = k + 1; i < len; ++i) lhs[i] = 0;
}
inline void merge(int lhs[], const int rhs[], int rlen) {
  static int temp[N];
  memcpy(temp, rhs, sizeof temp);
  for (int i = 0, j = 1, t = power(2, rlen); i < len;
       ++i, j = (long long)j * t % MOD)
    lhs[i] = (long long)lhs[i] * j % MOD;
  convolution(lhs, temp);
}
int main() {
  scanf("%I64d%d", &n, &k);
  if (n > k) return puts("0"), 0;
  for (int i = 0; i <= N; ++i)
    w[i] = Complex(cos(i * 2. * M_PI / N), sin(i * 2. * M_PI / N));
  static int fact[N], inv[N];
  fact[0] = 1;
  for (int i = 1; i < N; ++i) fact[i] = (long long)fact[i - 1] * i % MOD;
  inv[N - 1] = power(fact[N - 1], MOD - 2);
  for (int i = N - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1LL) % MOD;
  static int base[N], res[N];
  for (int i = 1; i <= k; ++i) base[i] = inv[i];
  len = 1;
  while (len <= 2 * k) len *= 2;
  res[0] = 1;
  for (int exp = n, cur = 1; exp; cur <<= 1, exp >>= 1) {
    if (exp & 1) merge(res, base, cur);
    merge(base, base, cur);
  }
  int ans = 0;
  for (int i = n; i <= k; ++i)
    ans = (ans + (long long)res[i] * fact[k] % MOD * inv[k - i]) % MOD;
  printf("%d\n", ans);
  return 0;
}

### 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 = 1 << 16, MOD = 1000000007;
struct Complex {
  double x, y;
  Complex(double _x = 0., double _y = 0.) : x(_x), y(_y) {}
  inline Complex conj() { return Complex(x, -y); }
};
inline Complex operator+(const Complex &lhs, const Complex &rhs) {
  return Complex(lhs.x + rhs.x, lhs.y + rhs.y);
}
inline Complex operator-(const Complex &lhs, const Complex &rhs) {
  return Complex(lhs.x - rhs.x, lhs.y - rhs.y);
}
inline Complex operator*(const Complex &lhs, const Complex &rhs) {
  return Complex(lhs.x * rhs.x - lhs.y * rhs.y, lhs.x * rhs.y + lhs.y * rhs.x);
}
const Complex I(0., 1.);
int len;
Complex w[N + 1];
void fft(Complex a[]) {
  for (register int i = 0, j = 0; i < len; ++i) {
    if (j < i) std::swap(a[i], a[j]);
    for (register int k = len >> 1; (j ^= k) < k;) k >>= 1;
  }
  for (int m = 2; m <= len; m *= 2) {
    int gap = m / 2, step = N / m;
    for (int i = 0; i < len; i += m) {
      Complex *o = w, *p = &a[i], *q = &a[i + gap];
      for (int j = gap; j--; ++p, ++q, o += step) {
        Complex u = *p, v = *o * *q;
        *p = u + v;
        *q = u - v;
      }
    }
  }
}
inline int power(int base, int exp) {
  int res = 1;
  for (; exp; exp >>= 1) {
    if (exp & 1) res = (long long)res * base % MOD;
    base = (long long)base * base % MOD;
  }
  return res;
}
long long n;
int k;
inline void convolution(int lhs[], const int rhs[]) {
  Complex a[N], b[N];
  for (int i = 0; i < len; ++i) a[i] = Complex(lhs[i] & 32767, lhs[i] >> 15);
  for (int i = 0; i < len; ++i) b[i] = Complex(rhs[i] & 32767, rhs[i] >> 15);
  fft(a);
  fft(b);
  static Complex res[4][N];
  for (int i = 0; i < len; ++i) {
    int j = (len - i) & (len - 1);
    Complex aLo = (a[i] + a[j].conj()) * Complex(.5, 0);
    Complex aHi = (a[i] - a[j].conj()) * Complex(0, -.5);
    Complex bLo = (b[i] + b[j].conj()) * Complex(.5, 0);
    Complex bHi = (b[i] - b[j].conj()) * Complex(0, -.5);
    res[0][i] = aLo * bLo;
    res[1][i] = aLo * bHi;
    res[2][i] = aHi * bLo;
    res[3][i] = aHi * bHi;
  }
  for (int i = 0; i < len; ++i) a[i] = res[0][i] + I * res[1][i];
  for (int i = 0; i < len; ++i) b[i] = res[2][i] + I * res[3][i];
  std::reverse(a + 1, a + len);
  std::reverse(b + 1, b + len);
  fft(a);
  fft(b);
  for (int i = 0; i <= k; ++i) {
    int lo = (long long)(a[i].x / len + .5) % MOD;
    int mid =
        ((long long)(a[i].y / len + .5) + (long long)(b[i].x / len + .5)) % MOD;
    int hi = (long long)(b[i].y / len + .5) % MOD;
    lhs[i] = (lo + ((long long)mid << 15) + ((long long)hi << 30)) % MOD;
  }
  for (int i = k + 1; i < len; ++i) lhs[i] = 0;
}
inline void merge(int lhs[], const int rhs[], int rlen) {
  static int temp[N];
  memcpy(temp, rhs, sizeof temp);
  for (int i = 0, j = 1, t = power(2, rlen); i < len;
       ++i, j = (long long)j * t % MOD)
    lhs[i] = (long long)lhs[i] * j % MOD;
  convolution(lhs, temp);
}
int main() {
  scanf("%I64d%d", &n, &k);
  if (n > k) return puts("0"), 0;
  for (int i = 0; i <= N; ++i)
    w[i] = Complex(cos(i * 2. * M_PI / N), sin(i * 2. * M_PI / N));
  static int fact[N], inv[N];
  fact[0] = 1;
  for (int i = 1; i < N; ++i) fact[i] = (long long)fact[i - 1] * i % MOD;
  inv[N - 1] = power(fact[N - 1], MOD - 2);
  for (int i = N - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1LL) % MOD;
  static int base[N], res[N];
  for (int i = 1; i <= k; ++i) base[i] = inv[i];
  len = 1;
  while (len <= 2 * k) len *= 2;
  res[0] = 1;
  for (int exp = n, cur = 1; exp; cur <<= 1, exp >>= 1) {
    if (exp & 1) merge(res, base, cur);
    merge(base, base, cur);
  }
  int ans = 0;
  for (int i = n; i <= k; ++i)
    ans = (ans + (long long)res[i] * fact[k] % MOD * inv[k - i]) % MOD;
  printf("%d\n", ans);
  return 0;
}

```