#include <bits/stdc++.h>
using namespace std;
template <int mod>
struct modulo {
  int w;
  operator int() const { return w; }
  modulo() {}
  modulo(int w) {
    this->w = w;
    fix();
  }
  template <class type>
  modulo(type w) {
    this->w = w % mod;
    fix();
  }
  void inline fix() {
    if (w >= mod || w < -mod) w %= mod;
    if (w < 0) w += mod;
  }
  inline modulo operator-() const { return mod - w; }
  inline modulo &operator+=(const modulo &b) {
    if ((w += b.w) >= mod) w -= mod;
    return *this;
  }
  inline modulo &operator-=(const modulo &b) {
    if ((w -= b.w) < 0) w += mod;
    return *this;
  }
  inline modulo &operator*=(const modulo &b) {
    w = (unsigned long long)w * b.w % mod;
    return *this;
  }
  inline modulo &operator/=(const modulo &b) { return *this *= inv(b); }
  friend modulo operator+(const modulo &a, const modulo &b) {
    return modulo(a) += b;
  }
  template <class type>
  friend modulo operator+(const modulo &a, const type &b) {
    return modulo(a) += b;
  }
  template <class type>
  friend modulo operator+(const type &a, const modulo &b) {
    return modulo(a) += b;
  }
  friend modulo operator-(const modulo &a, const modulo &b) {
    return modulo(a) -= b;
  }
  template <class type>
  friend modulo operator-(const modulo &a, const type &b) {
    return modulo(a) -= b;
  }
  template <class type>
  friend modulo operator-(const type &a, const modulo &b) {
    return modulo(a) -= b;
  }
  friend modulo operator*(const modulo &a, const modulo &b) {
    return modulo(a) *= b;
  }
  template <class type>
  friend modulo operator*(const modulo &a, const type &b) {
    return modulo(a) *= b;
  }
  template <class type>
  friend modulo operator*(const type &a, const modulo &b) {
    return modulo(a) *= b;
  }
  friend modulo operator/(const modulo &a, const modulo &b) {
    return modulo(a) /= b;
  }
  template <class type>
  friend modulo operator/(const modulo &a, const type &b) {
    return modulo(a) /= b;
  }
  template <class type>
  friend modulo operator/(const type &a, const modulo &b) {
    return modulo(a) /= b;
  }
  friend inline modulo inv(const modulo &w) {
    int a = w, m = mod, u = 0, v = 1, t;
    for (; a != 0; t = m / a, m -= t * a, swap(a, m), u -= t * v, swap(u, v))
      ;
    return u;
  }
  friend inline modulo pow(const modulo &w, int p) {
    if (!w) return 0;
    modulo a = w, r = 1;
    for (; p > 0; a *= a, p >>= 1)
      if (p & 1) r *= a;
    return r;
  }
};
const int mod = int(1e9) + 7;
void uadd(int &x, int y) {
  x += y - mod;
  x += (x >> 31) & mod;
}
void usub(int &x, int y) {
  x -= y;
  x += (x >> 31) & mod;
}
void umul(int &x, int y) { x = 1LL * x * y % mod; }
int add(int x, int y) {
  x += y - mod;
  x += (x >> 31) & mod;
  return x;
}
int sub(int x, int y) {
  x -= y;
  x += (x >> 31) & mod;
  return x;
}
int mul(int x, int y) { return 1LL * x * y % mod; }
int qp(int x, int n = mod - 2) {
  int ans = 1;
  for (; n; n >>= 1, umul(x, x))
    if (n & 1) umul(ans, x);
  return ans;
}
struct Comp {
 private:
  double x, y;

 public:
  Comp() : x(), y() {}
  Comp(double _x) : x(_x), y() {}
  Comp(double _x, double _y) : x(_x), y(_y) {}
  double real() { return x; }
  double imag() { return y; }
  Comp operator+(const Comp &o) const { return Comp(x + o.x, y + o.y); }
  Comp operator-(const Comp &o) const { return Comp(x - o.x, y - o.y); }
  Comp operator*(const Comp &o) const {
    return Comp(x * o.x - y * o.y, x * o.y + y * o.x);
  }
  Comp &operator+=(const Comp &o) { return *this = *this + o; }
  Comp &operator-=(const Comp &o) { return *this = *this - o; }
  Comp &operator*=(const Comp &o) { return *this = *this * o; }
  friend Comp conj(const Comp &x) { return Comp(x.x, -x.y); }
};
const int mxn = 1 << 16;
const double pi = acos(-1);
int r[mxn];
Comp w[mxn];
void fft_init(int n) {
  int k = 0;
  while ((1 << k) < n) ++k;
  for (int i = 1; i < n - 1; ++i) r[i] = r[i >> 1] >> 1 | (i & 1) << (k - 1);
  for (int h = 1; h < n; h <<= 1)
    for (int i = 0; i < h; ++i)
      w[h + i] = Comp(cos(pi * i / h), sin(pi * i / h));
}
void fft(Comp a[], int n, bool flag = 0) {
  for (int i = 1; i < n - 1; ++i)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int h = 1; h < n; h <<= 1) {
    for (int i = 0; i < n; i += (h << 1)) {
      Comp *w1 = a + i, *w2 = a + h + i, *pw = w + h, tmp;
      for (int j = 0; j < h; ++j, ++w1, ++w2, ++pw) {
        tmp = *w2 * *pw;
        *w2 = *w1 - tmp;
        *w1 += tmp;
      }
    }
  }
  if (flag) {
    reverse(a + 1, a + n);
    for (int i = 0; i < (int)(n); ++i) a[i] *= 1.0 / n;
  }
}
struct Poly : vector<int> {
  Poly() {}
  Poly(int n, int x = 0) {
    clear();
    resize(n, x);
  }
  void inline set_deg(int n) { resize(n + 1, 0); }
  Poly operator+(const Poly &o) const {
    Poly ans(max(size(), o.size()));
    for (int i = 0; i < (int)(size()); ++i) uadd(ans[i], at(i));
    for (int i = 0; i < (int)(o.size()); ++i) uadd(ans[i], o.at(i));
    return ans;
  }
  Poly operator-(const Poly &o) const {
    Poly ans(max(size(), o.size()));
    for (int i = 0; i < (int)(size()); ++i) uadd(ans[i], at(i));
    for (int i = 0; i < (int)(o.size()); ++i) usub(ans[i], o.at(i));
    return ans;
  }
  Poly operator*(int c) const {
    Poly ans(size());
    for (int i = 0; i < (int)(size()); ++i) ans[i] = mul(at(i), c);
    return ans;
  }
  Poly operator*(const Poly &o) const {
    if (max(size(), o.size()) <= 32) {
      Poly ans(size() + o.size() - 1);
      for (int i = 0; i < (int)(size()); ++i)
        for (int j = 0; j < (int)(o.size()); ++j)
          uadd(ans[i + j], mul(at(i), o.at(j)));
      return ans;
    } else {
      int n = size() + o.size() - 1;
      int sz = 1;
      while (sz < n) sz <<= 1;
      fft_init(sz);
      static Comp A[mxn], B[mxn];
      static Comp A0[mxn], A1[mxn], B0[mxn], B1[mxn];
      static Comp C[mxn];
      static Comp C0[mxn], C1[mxn], C2[mxn];
      for (int i = 0; i < (int)(sz); ++i) A[i] = B[i] = 0;
      for (int i = 0; i < (int)(size()); ++i)
        A[i] = Comp(at(i) >> 15, at(i) & 32767);
      for (int i = 0; i < (int)(o.size()); ++i)
        B[i] = Comp(o.at(i) >> 15, o.at(i) & 32767);
      fft(A, sz);
      fft(B, sz);
      for (int i = 0; i < (int)(sz); ++i) {
        int ni = i ? sz - i : 0;
        A0[i] = (A[i] + conj(A[ni])) * Comp(0.5, 0);
        A1[i] = (A[i] - conj(A[ni])) * Comp(0, -0.5);
        B0[i] = (B[i] + conj(B[ni])) * Comp(0.5, 0);
        B1[i] = (B[i] - conj(B[ni])) * Comp(0, -0.5);
      }
      for (int i = 0; i < (int)(sz); ++i) {
        C[i] = 0;
        C1[i] = 0;
      }
      for (int i = 0; i < (int)(sz); ++i) {
        C[i] += A0[i] * B0[i] * Comp(1, 0);
        C[i] += A1[i] * B1[i] * Comp(0, 1);
        C1[i] += A0[i] * B1[i] + A1[i] * B0[i];
      }
      fft(C, sz, 1);
      fft(C1, sz, 1);
      for (int i = 0; i < (int)(sz); ++i) {
        C0[i] = C[i].real();
        C2[i] = C[i].imag();
      }
      Poly ans(n);
      for (int i = 0; i < (int)(n); ++i) {
        uadd(ans[i], (((long long)(C0[i].real() + 0.5) % mod) << 30) % mod);
        uadd(ans[i], (((long long)(C1[i].real() + 0.5) % mod) << 15) % mod);
        uadd(ans[i], (((long long)(C2[i].real() + 0.5) % mod) << 0) % mod);
      }
      return ans;
    }
  }
};
const int nsz = 3e4, ksz = 3e4, sqrtsz = 500;
int k;
long long n;
modulo<mod> f[2][nsz + 5], pw[nsz + 5], ans;
Poly F, G, P[sqrtsz + 5];
void inline init(int n) {
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) f[0][i] = f[0][i - 1] * i;
  f[1][n] = 1 / f[0][n];
  for (int i = n - 1; i >= 0; --i) f[1][i] = f[1][i + 1] * (i + 1);
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * 2;
}
void inline solve() {
  if (n > k) return (void)(ans = 0);
  int b = 0, B = ceil(sqrt(n));
  F.set_deg(k), F[0] = 1;
  for (int b = 0; b < B; ++b) {
    P[b].set_deg(k);
    for (int i = 1; i <= k; ++i)
      P[b][i] = (long long)f[1][i] * pow(pw[b], i) % mod;
    if (b > 0) P[b] = P[b] * P[b - 1];
    P[b].set_deg(k);
  }
  for (b = 0; b + B <= n; b += B) {
    for (int i = 0; i <= k; ++i) F[i] = (long long)F[i] * pow(pw[B], i) % mod;
    F = F * P[B - 1];
    F.set_deg(k);
  }
  int d = n - b;
  if (d == 0)
    G = F;
  else {
    for (int i = 0; i <= k; ++i) F[i] = (long long)F[i] * pow(pw[d], i) % mod;
    G = F * P[d - 1];
  }
  for (int i = 0; i <= k; ++i)
    G[i] = (long long)G[i] * f[0][k] % mod * f[1][k - i] % mod;
  for (int i = 0; i <= k; ++i) ans += G[i];
}
int main() {
  scanf("%lld%d", &n, &k);
  init(k);
  solve();
  printf("%d\n", ans.w);
  return 0;
}

### Prompt

Please provide a CPP coded solution 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;
template <int mod>
struct modulo {
  int w;
  operator int() const { return w; }
  modulo() {}
  modulo(int w) {
    this->w = w;
    fix();
  }
  template <class type>
  modulo(type w) {
    this->w = w % mod;
    fix();
  }
  void inline fix() {
    if (w >= mod || w < -mod) w %= mod;
    if (w < 0) w += mod;
  }
  inline modulo operator-() const { return mod - w; }
  inline modulo &operator+=(const modulo &b) {
    if ((w += b.w) >= mod) w -= mod;
    return *this;
  }
  inline modulo &operator-=(const modulo &b) {
    if ((w -= b.w) < 0) w += mod;
    return *this;
  }
  inline modulo &operator*=(const modulo &b) {
    w = (unsigned long long)w * b.w % mod;
    return *this;
  }
  inline modulo &operator/=(const modulo &b) { return *this *= inv(b); }
  friend modulo operator+(const modulo &a, const modulo &b) {
    return modulo(a) += b;
  }
  template <class type>
  friend modulo operator+(const modulo &a, const type &b) {
    return modulo(a) += b;
  }
  template <class type>
  friend modulo operator+(const type &a, const modulo &b) {
    return modulo(a) += b;
  }
  friend modulo operator-(const modulo &a, const modulo &b) {
    return modulo(a) -= b;
  }
  template <class type>
  friend modulo operator-(const modulo &a, const type &b) {
    return modulo(a) -= b;
  }
  template <class type>
  friend modulo operator-(const type &a, const modulo &b) {
    return modulo(a) -= b;
  }
  friend modulo operator*(const modulo &a, const modulo &b) {
    return modulo(a) *= b;
  }
  template <class type>
  friend modulo operator*(const modulo &a, const type &b) {
    return modulo(a) *= b;
  }
  template <class type>
  friend modulo operator*(const type &a, const modulo &b) {
    return modulo(a) *= b;
  }
  friend modulo operator/(const modulo &a, const modulo &b) {
    return modulo(a) /= b;
  }
  template <class type>
  friend modulo operator/(const modulo &a, const type &b) {
    return modulo(a) /= b;
  }
  template <class type>
  friend modulo operator/(const type &a, const modulo &b) {
    return modulo(a) /= b;
  }
  friend inline modulo inv(const modulo &w) {
    int a = w, m = mod, u = 0, v = 1, t;
    for (; a != 0; t = m / a, m -= t * a, swap(a, m), u -= t * v, swap(u, v))
      ;
    return u;
  }
  friend inline modulo pow(const modulo &w, int p) {
    if (!w) return 0;
    modulo a = w, r = 1;
    for (; p > 0; a *= a, p >>= 1)
      if (p & 1) r *= a;
    return r;
  }
};
const int mod = int(1e9) + 7;
void uadd(int &x, int y) {
  x += y - mod;
  x += (x >> 31) & mod;
}
void usub(int &x, int y) {
  x -= y;
  x += (x >> 31) & mod;
}
void umul(int &x, int y) { x = 1LL * x * y % mod; }
int add(int x, int y) {
  x += y - mod;
  x += (x >> 31) & mod;
  return x;
}
int sub(int x, int y) {
  x -= y;
  x += (x >> 31) & mod;
  return x;
}
int mul(int x, int y) { return 1LL * x * y % mod; }
int qp(int x, int n = mod - 2) {
  int ans = 1;
  for (; n; n >>= 1, umul(x, x))
    if (n & 1) umul(ans, x);
  return ans;
}
struct Comp {
 private:
  double x, y;

 public:
  Comp() : x(), y() {}
  Comp(double _x) : x(_x), y() {}
  Comp(double _x, double _y) : x(_x), y(_y) {}
  double real() { return x; }
  double imag() { return y; }
  Comp operator+(const Comp &o) const { return Comp(x + o.x, y + o.y); }
  Comp operator-(const Comp &o) const { return Comp(x - o.x, y - o.y); }
  Comp operator*(const Comp &o) const {
    return Comp(x * o.x - y * o.y, x * o.y + y * o.x);
  }
  Comp &operator+=(const Comp &o) { return *this = *this + o; }
  Comp &operator-=(const Comp &o) { return *this = *this - o; }
  Comp &operator*=(const Comp &o) { return *this = *this * o; }
  friend Comp conj(const Comp &x) { return Comp(x.x, -x.y); }
};
const int mxn = 1 << 16;
const double pi = acos(-1);
int r[mxn];
Comp w[mxn];
void fft_init(int n) {
  int k = 0;
  while ((1 << k) < n) ++k;
  for (int i = 1; i < n - 1; ++i) r[i] = r[i >> 1] >> 1 | (i & 1) << (k - 1);
  for (int h = 1; h < n; h <<= 1)
    for (int i = 0; i < h; ++i)
      w[h + i] = Comp(cos(pi * i / h), sin(pi * i / h));
}
void fft(Comp a[], int n, bool flag = 0) {
  for (int i = 1; i < n - 1; ++i)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int h = 1; h < n; h <<= 1) {
    for (int i = 0; i < n; i += (h << 1)) {
      Comp *w1 = a + i, *w2 = a + h + i, *pw = w + h, tmp;
      for (int j = 0; j < h; ++j, ++w1, ++w2, ++pw) {
        tmp = *w2 * *pw;
        *w2 = *w1 - tmp;
        *w1 += tmp;
      }
    }
  }
  if (flag) {
    reverse(a + 1, a + n);
    for (int i = 0; i < (int)(n); ++i) a[i] *= 1.0 / n;
  }
}
struct Poly : vector<int> {
  Poly() {}
  Poly(int n, int x = 0) {
    clear();
    resize(n, x);
  }
  void inline set_deg(int n) { resize(n + 1, 0); }
  Poly operator+(const Poly &o) const {
    Poly ans(max(size(), o.size()));
    for (int i = 0; i < (int)(size()); ++i) uadd(ans[i], at(i));
    for (int i = 0; i < (int)(o.size()); ++i) uadd(ans[i], o.at(i));
    return ans;
  }
  Poly operator-(const Poly &o) const {
    Poly ans(max(size(), o.size()));
    for (int i = 0; i < (int)(size()); ++i) uadd(ans[i], at(i));
    for (int i = 0; i < (int)(o.size()); ++i) usub(ans[i], o.at(i));
    return ans;
  }
  Poly operator*(int c) const {
    Poly ans(size());
    for (int i = 0; i < (int)(size()); ++i) ans[i] = mul(at(i), c);
    return ans;
  }
  Poly operator*(const Poly &o) const {
    if (max(size(), o.size()) <= 32) {
      Poly ans(size() + o.size() - 1);
      for (int i = 0; i < (int)(size()); ++i)
        for (int j = 0; j < (int)(o.size()); ++j)
          uadd(ans[i + j], mul(at(i), o.at(j)));
      return ans;
    } else {
      int n = size() + o.size() - 1;
      int sz = 1;
      while (sz < n) sz <<= 1;
      fft_init(sz);
      static Comp A[mxn], B[mxn];
      static Comp A0[mxn], A1[mxn], B0[mxn], B1[mxn];
      static Comp C[mxn];
      static Comp C0[mxn], C1[mxn], C2[mxn];
      for (int i = 0; i < (int)(sz); ++i) A[i] = B[i] = 0;
      for (int i = 0; i < (int)(size()); ++i)
        A[i] = Comp(at(i) >> 15, at(i) & 32767);
      for (int i = 0; i < (int)(o.size()); ++i)
        B[i] = Comp(o.at(i) >> 15, o.at(i) & 32767);
      fft(A, sz);
      fft(B, sz);
      for (int i = 0; i < (int)(sz); ++i) {
        int ni = i ? sz - i : 0;
        A0[i] = (A[i] + conj(A[ni])) * Comp(0.5, 0);
        A1[i] = (A[i] - conj(A[ni])) * Comp(0, -0.5);
        B0[i] = (B[i] + conj(B[ni])) * Comp(0.5, 0);
        B1[i] = (B[i] - conj(B[ni])) * Comp(0, -0.5);
      }
      for (int i = 0; i < (int)(sz); ++i) {
        C[i] = 0;
        C1[i] = 0;
      }
      for (int i = 0; i < (int)(sz); ++i) {
        C[i] += A0[i] * B0[i] * Comp(1, 0);
        C[i] += A1[i] * B1[i] * Comp(0, 1);
        C1[i] += A0[i] * B1[i] + A1[i] * B0[i];
      }
      fft(C, sz, 1);
      fft(C1, sz, 1);
      for (int i = 0; i < (int)(sz); ++i) {
        C0[i] = C[i].real();
        C2[i] = C[i].imag();
      }
      Poly ans(n);
      for (int i = 0; i < (int)(n); ++i) {
        uadd(ans[i], (((long long)(C0[i].real() + 0.5) % mod) << 30) % mod);
        uadd(ans[i], (((long long)(C1[i].real() + 0.5) % mod) << 15) % mod);
        uadd(ans[i], (((long long)(C2[i].real() + 0.5) % mod) << 0) % mod);
      }
      return ans;
    }
  }
};
const int nsz = 3e4, ksz = 3e4, sqrtsz = 500;
int k;
long long n;
modulo<mod> f[2][nsz + 5], pw[nsz + 5], ans;
Poly F, G, P[sqrtsz + 5];
void inline init(int n) {
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) f[0][i] = f[0][i - 1] * i;
  f[1][n] = 1 / f[0][n];
  for (int i = n - 1; i >= 0; --i) f[1][i] = f[1][i + 1] * (i + 1);
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * 2;
}
void inline solve() {
  if (n > k) return (void)(ans = 0);
  int b = 0, B = ceil(sqrt(n));
  F.set_deg(k), F[0] = 1;
  for (int b = 0; b < B; ++b) {
    P[b].set_deg(k);
    for (int i = 1; i <= k; ++i)
      P[b][i] = (long long)f[1][i] * pow(pw[b], i) % mod;
    if (b > 0) P[b] = P[b] * P[b - 1];
    P[b].set_deg(k);
  }
  for (b = 0; b + B <= n; b += B) {
    for (int i = 0; i <= k; ++i) F[i] = (long long)F[i] * pow(pw[B], i) % mod;
    F = F * P[B - 1];
    F.set_deg(k);
  }
  int d = n - b;
  if (d == 0)
    G = F;
  else {
    for (int i = 0; i <= k; ++i) F[i] = (long long)F[i] * pow(pw[d], i) % mod;
    G = F * P[d - 1];
  }
  for (int i = 0; i <= k; ++i)
    G[i] = (long long)G[i] * f[0][k] % mod * f[1][k - i] % mod;
  for (int i = 0; i <= k; ++i) ans += G[i];
}
int main() {
  scanf("%lld%d", &n, &k);
  init(k);
  solve();
  printf("%d\n", ans.w);
  return 0;
}

```