#include <bits/stdc++.h>
using namespace std;
namespace FastFourierTransform {
const long double PI = acosl(-1);
struct Complex {
  long double real, imag;
  Complex(const long double _real = 0, const long double _imag = 0)
      : real(_real), imag(_imag) {}
  Complex operator*(const Complex& other) const {
    return Complex(real * other.real - imag * other.imag,
                   real * other.imag + imag * other.real);
  }
  void operator*=(const Complex& other) {
    long double aux = real * other.real - imag * other.imag;
    imag = real * other.imag + imag * other.real;
    real = aux;
  }
  Complex operator+(const Complex& other) const {
    return Complex(real + other.real, imag + other.imag);
  }
  void operator+=(const Complex& other) {
    real += other.real;
    imag += other.imag;
  }
  Complex operator-(const Complex& other) const {
    return Complex(real - other.real, imag - other.imag);
  }
  void operator-=(const Complex& other) {
    real -= other.real;
    imag -= other.imag;
  }
  void operator/=(const long double other) {
    real /= other;
    imag /= other;
  }
};
void fft(vector<Complex>& a, bool invert) {
  int n = a.size();
  for (int i = 1, j = 0; i < n; ++i) {
    int bit = n >> 1;
    for (; j >= bit; bit >>= 1) {
      j -= bit;
    }
    j += bit;
    if (i < j) {
      swap(a[i], a[j]);
    }
  }
  for (int len = 2; len <= n; len <<= 1) {
    int halfLen = len >> 1;
    long double angle = 2 * PI / len * (invert ? -1 : 1);
    Complex wl(cos(angle), sin(angle));
    for (int i = 0; i < n; i += len) {
      Complex w(1);
      for (int j = 0; j < halfLen; ++j) {
        Complex u = a[i + j], v = w * a[i + j + halfLen];
        a[i + j] = u + v;
        a[i + j + halfLen] = u - v;
        w *= wl;
      }
    }
  }
  if (invert) {
    for (int i = 0; i < n; ++i) {
      a[i] /= n;
    }
  }
}
vector<long long> multiply(const vector<long long>& a,
                           const vector<long long>& b) {
  int n1 = a.size(), n2 = b.size();
  int m = 1;
  while (m < n1 || m < n2) m <<= 1;
  m <<= 1;
  vector<Complex> fa(m, 0), fb(m, 0);
  for (int i = 0; i < n1; ++i) {
    fa[i] = a[i];
  }
  for (int i = 0; i < n2; ++i) {
    fb[i] = b[i];
  }
  fft(fa, false);
  fft(fb, false);
  for (int i = 0; i < m; ++i) {
    fa[i] *= fb[i];
  }
  fft(fa, true);
  vector<long long> res(m);
  for (int i = 0; i < m; ++i) {
    res[i] = (long long)(fa[i].real + 0.5);
  }
  return res;
}
vector<long long> modMultiply(const vector<long long>& a,
                              const vector<long long>& b, const int MOD) {
  assert(a.size() == b.size());
  int n = (int)a.size();
  int SQ = sqrt(MOD);
  vector<long long> s1(n), s2(n), s3(n), s4(n);
  for (int i = 0; i < n; ++i) {
    s1[i] = a[i] % SQ;
    s2[i] = a[i] / SQ;
    s3[i] = b[i] % SQ;
    s4[i] = b[i] / SQ;
  }
  vector<long long> r1 = multiply(s1, s3);
  vector<long long> r2 = multiply(s1, s4);
  vector<long long> r3 = multiply(s2, s3);
  vector<long long> r4 = multiply(s2, s4);
  r1.resize(n);
  for (int i = 0; i < n; ++i) {
    r1[i] += (r2[i] + r3[i]) % MOD * SQ % MOD;
    r1[i] += r4[i] % MOD * SQ % MOD * SQ % MOD;
    r1[i] %= MOD;
  }
  return r1;
}
}  // namespace FastFourierTransform
const int N = 30001, MOD = 1000000007;
long long fac[N], inv[N];
long long modPow(long long a, long long b) {
  long long ans = 1;
  for (long long i = 1; i <= b; i *= 2) {
    if (b & i) ans = ans * a % MOD;
    a = a * a % MOD;
  }
  return ans;
}
void precalc() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
  inv[N - 1] = modPow(fac[N - 1], MOD - 2);
  for (int i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
int C(int n, int p) { return fac[n] * inv[p] % MOD * inv[n - p] % MOD; }
vector<long long> multiply(vector<long long> A, int x, vector<long long> B,
                           int y) {
  for (int i = 0; i < (int)A.size(); i++)
    A[i] = A[i] * inv[i] % MOD * modPow(2, 1LL * i * y) % MOD;
  for (int i = 0; i < (int)B.size(); i++) B[i] = B[i] * inv[i] % MOD;
  vector<long long> ans = FastFourierTransform::modMultiply(A, B, MOD);
  for (int i = 0; i < (int)ans.size(); i++) ans[i] = ans[i] * fac[i] % MOD;
  return ans;
}
vector<long long> solve(int n, int m) {
  vector<long long> ans(m + 1, 0), P(m + 1, 1);
  ans[0] = 1;
  P[0] = 0;
  for (int i = 1; i <= m; i *= 2) {
    if ((n & i)) ans = multiply(ans, n & (i - 1), P, i);
    P = multiply(P, i, P, i);
  }
  return ans;
}
int main() {
  precalc();
  long long _n;
  int k;
  scanf("%lld %d", &_n, &k);
  if (_n > k) {
    printf("0\n");
    exit(0);
  }
  int n = (int)_n;
  vector<long long> dp = solve(n, k);
  long long ans = 0;
  for (int i = 0; i <= k; i++) ans = (ans + dp[i] * C(k, i) % MOD) % MOD;
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
namespace FastFourierTransform {
const long double PI = acosl(-1);
struct Complex {
  long double real, imag;
  Complex(const long double _real = 0, const long double _imag = 0)
      : real(_real), imag(_imag) {}
  Complex operator*(const Complex& other) const {
    return Complex(real * other.real - imag * other.imag,
                   real * other.imag + imag * other.real);
  }
  void operator*=(const Complex& other) {
    long double aux = real * other.real - imag * other.imag;
    imag = real * other.imag + imag * other.real;
    real = aux;
  }
  Complex operator+(const Complex& other) const {
    return Complex(real + other.real, imag + other.imag);
  }
  void operator+=(const Complex& other) {
    real += other.real;
    imag += other.imag;
  }
  Complex operator-(const Complex& other) const {
    return Complex(real - other.real, imag - other.imag);
  }
  void operator-=(const Complex& other) {
    real -= other.real;
    imag -= other.imag;
  }
  void operator/=(const long double other) {
    real /= other;
    imag /= other;
  }
};
void fft(vector<Complex>& a, bool invert) {
  int n = a.size();
  for (int i = 1, j = 0; i < n; ++i) {
    int bit = n >> 1;
    for (; j >= bit; bit >>= 1) {
      j -= bit;
    }
    j += bit;
    if (i < j) {
      swap(a[i], a[j]);
    }
  }
  for (int len = 2; len <= n; len <<= 1) {
    int halfLen = len >> 1;
    long double angle = 2 * PI / len * (invert ? -1 : 1);
    Complex wl(cos(angle), sin(angle));
    for (int i = 0; i < n; i += len) {
      Complex w(1);
      for (int j = 0; j < halfLen; ++j) {
        Complex u = a[i + j], v = w * a[i + j + halfLen];
        a[i + j] = u + v;
        a[i + j + halfLen] = u - v;
        w *= wl;
      }
    }
  }
  if (invert) {
    for (int i = 0; i < n; ++i) {
      a[i] /= n;
    }
  }
}
vector<long long> multiply(const vector<long long>& a,
                           const vector<long long>& b) {
  int n1 = a.size(), n2 = b.size();
  int m = 1;
  while (m < n1 || m < n2) m <<= 1;
  m <<= 1;
  vector<Complex> fa(m, 0), fb(m, 0);
  for (int i = 0; i < n1; ++i) {
    fa[i] = a[i];
  }
  for (int i = 0; i < n2; ++i) {
    fb[i] = b[i];
  }
  fft(fa, false);
  fft(fb, false);
  for (int i = 0; i < m; ++i) {
    fa[i] *= fb[i];
  }
  fft(fa, true);
  vector<long long> res(m);
  for (int i = 0; i < m; ++i) {
    res[i] = (long long)(fa[i].real + 0.5);
  }
  return res;
}
vector<long long> modMultiply(const vector<long long>& a,
                              const vector<long long>& b, const int MOD) {
  assert(a.size() == b.size());
  int n = (int)a.size();
  int SQ = sqrt(MOD);
  vector<long long> s1(n), s2(n), s3(n), s4(n);
  for (int i = 0; i < n; ++i) {
    s1[i] = a[i] % SQ;
    s2[i] = a[i] / SQ;
    s3[i] = b[i] % SQ;
    s4[i] = b[i] / SQ;
  }
  vector<long long> r1 = multiply(s1, s3);
  vector<long long> r2 = multiply(s1, s4);
  vector<long long> r3 = multiply(s2, s3);
  vector<long long> r4 = multiply(s2, s4);
  r1.resize(n);
  for (int i = 0; i < n; ++i) {
    r1[i] += (r2[i] + r3[i]) % MOD * SQ % MOD;
    r1[i] += r4[i] % MOD * SQ % MOD * SQ % MOD;
    r1[i] %= MOD;
  }
  return r1;
}
}  // namespace FastFourierTransform
const int N = 30001, MOD = 1000000007;
long long fac[N], inv[N];
long long modPow(long long a, long long b) {
  long long ans = 1;
  for (long long i = 1; i <= b; i *= 2) {
    if (b & i) ans = ans * a % MOD;
    a = a * a % MOD;
  }
  return ans;
}
void precalc() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
  inv[N - 1] = modPow(fac[N - 1], MOD - 2);
  for (int i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
int C(int n, int p) { return fac[n] * inv[p] % MOD * inv[n - p] % MOD; }
vector<long long> multiply(vector<long long> A, int x, vector<long long> B,
                           int y) {
  for (int i = 0; i < (int)A.size(); i++)
    A[i] = A[i] * inv[i] % MOD * modPow(2, 1LL * i * y) % MOD;
  for (int i = 0; i < (int)B.size(); i++) B[i] = B[i] * inv[i] % MOD;
  vector<long long> ans = FastFourierTransform::modMultiply(A, B, MOD);
  for (int i = 0; i < (int)ans.size(); i++) ans[i] = ans[i] * fac[i] % MOD;
  return ans;
}
vector<long long> solve(int n, int m) {
  vector<long long> ans(m + 1, 0), P(m + 1, 1);
  ans[0] = 1;
  P[0] = 0;
  for (int i = 1; i <= m; i *= 2) {
    if ((n & i)) ans = multiply(ans, n & (i - 1), P, i);
    P = multiply(P, i, P, i);
  }
  return ans;
}
int main() {
  precalc();
  long long _n;
  int k;
  scanf("%lld %d", &_n, &k);
  if (_n > k) {
    printf("0\n");
    exit(0);
  }
  int n = (int)_n;
  vector<long long> dp = solve(n, k);
  long long ans = 0;
  for (int i = 0; i <= k; i++) ans = (ans + dp[i] * C(k, i) % MOD) % MOD;
  printf("%lld\n", ans);
  return 0;
}

```