#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
void chkmin(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
void chkmax(T1 &x, T2 y) {
  if (x < y) x = y;
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T neg = 1;
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  x *= neg;
}
const int MOD = 1e9 + 7;
const int M = 1 << 15;
const int MAGIC = 73741817;
const int MAXK = 3e4;
const int MAXP = 1 << 17;
const int LOG_N = 16;
const long double Pi = acos(-1);
int qpow(int x, long long e) {
  int ret = 1;
  for (; e; e >>= 1, x = 1ll * x * x % MOD)
    if (e & 1) ret = 1ll * ret * x % MOD;
  return ret;
}
struct comp {
  long double x, y;
  comp() { x = y = 0; }
  comp(long double _x, long double _y) {
    x = _x;
    y = _y;
  }
  comp operator+(const comp &rhs) { return comp(x + rhs.x, y + rhs.y); }
  comp operator-(const comp &rhs) { return comp(x - rhs.x, y - rhs.y); }
  comp operator*(const comp &rhs) {
    return comp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  }
} A[MAXP + 5], B[MAXP + 5], C[MAXP + 5], D[MAXP + 5];
int E[MAXP + 5], F[MAXP + 5];
int LEN = 1, LOG = 0, rev[MAXP + 5];
void FFT(comp *a, int len, int type) {
  int lg = log2(len);
  for (int i = 0; i < len; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  for (int i = 0; i < len; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 2; i <= len; i <<= 1) {
    comp W(cos(2 * Pi / i), type * sin(2 * Pi / i));
    for (int j = 0; j < len; j += i) {
      comp w(1, 0);
      for (int k = 0; k < (i >> 1); k++, w = w * W) {
        comp X = a[j + k], Y = w * a[(i >> 1) + j + k];
        a[j + k] = X + Y;
        a[(i >> 1) + j + k] = X - Y;
      }
    }
  }
  if (type == -1)
    for (int i = 0; i < len; i++) a[i].x = (long long)(a[i].x / len + 0.5);
}
void polymul(int *a, int *b, int *c, int len) {
  for (int i = 0; i < len; i++)
    A[i].x = a[i] / M, B[i].x = a[i] % M, C[i].x = b[i] / M, D[i].x = b[i] % M;
  FFT(A, len, 1);
  FFT(B, len, 1);
  FFT(C, len, 1);
  FFT(D, len, 1);
  for (int i = 0; i < len; i++) {
    comp t1 = A[i] * C[i], t2 = B[i] * D[i];
    B[i] = A[i] * D[i] + B[i] * C[i];
    A[i] = t1;
    C[i] = t2;
  }
  FFT(A, len, -1);
  FFT(B, len, -1);
  FFT(C, len, -1);
  for (int i = 0; i < len; i++)
    c[i] = ((1ll * (long long)(A[i].x) % MOD * MAGIC % MOD +
             1ll * (long long)(B[i].x) % MOD * M % MOD) %
                MOD +
            (long long)(C[i].x)) %
           MOD;
  for (int i = 0; i < len; i++) A[i] = B[i] = C[i] = D[i] = comp(0, 0);
}
long long n;
int k;
int fac[MAXK + 5], ifac[MAXK + 5];
int binom(int x, int y) {
  return 1ll * fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}
void merge(int *a, int *b, int *c, long long x) {
  for (int i = 0; i <= k; i++)
    E[i] = 1ll * a[i] * ifac[i] % MOD *
           qpow(2, 1ll * x % (MOD - 2) * i % (MOD - 2)) % MOD;
  for (int i = 0; i <= k; i++) F[i] = 1ll * b[i] * ifac[i] % MOD;
  polymul(E, F, E, LEN);
  for (int i = 0; i <= k; i++) c[i] = 1ll * E[i] * fac[i] % MOD;
  for (int i = 0; i < LEN; i++) E[i] = F[i] = 0;
}
int a[MAXP + 5], b[MAXP + 5];
int main() {
  scanf("%lld%d", &n, &k);
  fac[0] = 1;
  if (n > k) return puts("0"), 0;
  for (int i = 1; i <= k; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
  ifac[k] = qpow(fac[k], MOD - 2);
  for (int i = k - 1; ~i; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % MOD;
  while (LEN <= k + k) LEN <<= 1;
  a[0] = 1;
  for (int i = 1; i <= k; i++) b[i] = 1;
  long long ca = 0, cb = 1;
  for (int i = 0; i <= LOG_N; i++, merge(b, b, b, cb), cb <<= 1)
    if (n >> i & 1) ca |= cb, merge(a, b, a, cb);
  int ans = 0;
  for (int i = 1; i <= k; i++)
    ans = (ans + 1ll * a[i] * binom(k, i) % MOD) % MOD;
  printf("%d\n", ans);
  return 0;
}

### Prompt

Your challenge is to write 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;
template <typename T1, typename T2>
void chkmin(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
void chkmax(T1 &x, T2 y) {
  if (x < y) x = y;
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T neg = 1;
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  x *= neg;
}
const int MOD = 1e9 + 7;
const int M = 1 << 15;
const int MAGIC = 73741817;
const int MAXK = 3e4;
const int MAXP = 1 << 17;
const int LOG_N = 16;
const long double Pi = acos(-1);
int qpow(int x, long long e) {
  int ret = 1;
  for (; e; e >>= 1, x = 1ll * x * x % MOD)
    if (e & 1) ret = 1ll * ret * x % MOD;
  return ret;
}
struct comp {
  long double x, y;
  comp() { x = y = 0; }
  comp(long double _x, long double _y) {
    x = _x;
    y = _y;
  }
  comp operator+(const comp &rhs) { return comp(x + rhs.x, y + rhs.y); }
  comp operator-(const comp &rhs) { return comp(x - rhs.x, y - rhs.y); }
  comp operator*(const comp &rhs) {
    return comp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  }
} A[MAXP + 5], B[MAXP + 5], C[MAXP + 5], D[MAXP + 5];
int E[MAXP + 5], F[MAXP + 5];
int LEN = 1, LOG = 0, rev[MAXP + 5];
void FFT(comp *a, int len, int type) {
  int lg = log2(len);
  for (int i = 0; i < len; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  for (int i = 0; i < len; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 2; i <= len; i <<= 1) {
    comp W(cos(2 * Pi / i), type * sin(2 * Pi / i));
    for (int j = 0; j < len; j += i) {
      comp w(1, 0);
      for (int k = 0; k < (i >> 1); k++, w = w * W) {
        comp X = a[j + k], Y = w * a[(i >> 1) + j + k];
        a[j + k] = X + Y;
        a[(i >> 1) + j + k] = X - Y;
      }
    }
  }
  if (type == -1)
    for (int i = 0; i < len; i++) a[i].x = (long long)(a[i].x / len + 0.5);
}
void polymul(int *a, int *b, int *c, int len) {
  for (int i = 0; i < len; i++)
    A[i].x = a[i] / M, B[i].x = a[i] % M, C[i].x = b[i] / M, D[i].x = b[i] % M;
  FFT(A, len, 1);
  FFT(B, len, 1);
  FFT(C, len, 1);
  FFT(D, len, 1);
  for (int i = 0; i < len; i++) {
    comp t1 = A[i] * C[i], t2 = B[i] * D[i];
    B[i] = A[i] * D[i] + B[i] * C[i];
    A[i] = t1;
    C[i] = t2;
  }
  FFT(A, len, -1);
  FFT(B, len, -1);
  FFT(C, len, -1);
  for (int i = 0; i < len; i++)
    c[i] = ((1ll * (long long)(A[i].x) % MOD * MAGIC % MOD +
             1ll * (long long)(B[i].x) % MOD * M % MOD) %
                MOD +
            (long long)(C[i].x)) %
           MOD;
  for (int i = 0; i < len; i++) A[i] = B[i] = C[i] = D[i] = comp(0, 0);
}
long long n;
int k;
int fac[MAXK + 5], ifac[MAXK + 5];
int binom(int x, int y) {
  return 1ll * fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}
void merge(int *a, int *b, int *c, long long x) {
  for (int i = 0; i <= k; i++)
    E[i] = 1ll * a[i] * ifac[i] % MOD *
           qpow(2, 1ll * x % (MOD - 2) * i % (MOD - 2)) % MOD;
  for (int i = 0; i <= k; i++) F[i] = 1ll * b[i] * ifac[i] % MOD;
  polymul(E, F, E, LEN);
  for (int i = 0; i <= k; i++) c[i] = 1ll * E[i] * fac[i] % MOD;
  for (int i = 0; i < LEN; i++) E[i] = F[i] = 0;
}
int a[MAXP + 5], b[MAXP + 5];
int main() {
  scanf("%lld%d", &n, &k);
  fac[0] = 1;
  if (n > k) return puts("0"), 0;
  for (int i = 1; i <= k; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
  ifac[k] = qpow(fac[k], MOD - 2);
  for (int i = k - 1; ~i; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % MOD;
  while (LEN <= k + k) LEN <<= 1;
  a[0] = 1;
  for (int i = 1; i <= k; i++) b[i] = 1;
  long long ca = 0, cb = 1;
  for (int i = 0; i <= LOG_N; i++, merge(b, b, b, cb), cb <<= 1)
    if (n >> i & 1) ca |= cb, merge(a, b, a, cb);
  int ans = 0;
  for (int i = 1; i <= k; i++)
    ans = (ans + 1ll * a[i] * binom(k, i) % MOD) % MOD;
  printf("%d\n", ans);
  return 0;
}

```