#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T alex(T x) {
  return (x > 0) ? x : -x;
}
template <class T>
void read(T& x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while ((ch < 48 || ch > 57) && ch != 45) ch = getchar();
  if (ch == 45) f = -1, ch = getchar();
  while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = getchar();
  x *= f;
}
long long n;
int k;
int f[17][65536];
int fac[65536], inv[65536], pow2[65536];
int power(int a, int b, int p) {
  int s = 1, w = a;
  while (b) {
    if (b & 1) s = (long long)s * w % p;
    w = (long long)w * w % p;
    b >>= 1;
  }
  return s;
}
struct CP {
  double x, y;
  CP() {}
  CP(double x, double y) : x(x), y(y) {}
  CP operator+(const CP& p) const { return CP(x + p.x, y + p.y); }
  CP operator-(const CP& p) const { return CP(x - p.x, y - p.y); }
  CP operator*(const CP& p) const {
    return CP(x * p.x - y * p.y, x * p.y + y * p.x);
  }
  CP operator*(const double& p) const { return CP(x * p, y * p); }
  CP operator/(const double& p) const { return CP(x / p, y / p); }
};
int getC(int n, int m) {
  return (long long)fac[n] * inv[m] % 1000000007 * inv[n - m] % 1000000007;
}
int l, r[65536], all;
CP A[65536], B[65536], C[65536], D[65536];
CP w[65536];
void print(CP* a) {
  for (int i = (0); i < (all); i++) printf("(%.3f %.3f)", a[i].x, a[i].y);
  printf("\n");
}
CP _w1[17][65536], _w2[17][65536];
void init(int l) {
  for (int i = (0); i < (l); i++) {
    for (int k = (0); k <= (1 << i); k++)
      _w1[i][k] = CP(cos(PI / (1 << i) * k), sin(PI / (1 << i) * k));
    for (int k = (0); k <= (1 << i); k++)
      _w2[i][k] = CP(cos(PI / (1 << i) * k), -sin(PI / (1 << i) * k));
  }
}
void FFT(CP* a, int n) {
  for (int i = (0); i < (n); i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1, z = 0; i < n; i <<= 1, z++) {
    for (int j = 0, del = i << 1; j < n; j += del) {
      for (int k = (0); k < (i); k++) {
        register CP x = a[j + k], y = _w1[z][k] * a[j + k + i];
        a[j + k] = x + y;
        a[j + k + i] = x - y;
      }
    }
  }
}
void DFT(CP* a, int n) {
  for (int i = (0); i < (n); i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1, z = 0; i < n; i <<= 1, z++) {
    for (int j = 0, del = i << 1; j < n; j += del) {
      for (int k = (0); k < (i); k++) {
        register CP x = a[j + k], y = _w2[z][k] * a[j + k + i];
        a[j + k] = x + y, a[j + k + i] = x - y;
      }
    }
  }
  for (int i = (0); i < (n); i++) a[i] = a[i] / n;
}
int F[65536], G[65536];
CP P[65536], Q[65536], R[65536];
void mul(int* f, int* a, int* b, int idx) {
  memset(A, 0, sizeof(A));
  memset(B, 0, sizeof(B));
  memset(C, 0, sizeof(C));
  memset(D, 0, sizeof(D));
  memset(P, 0, sizeof(P));
  memset(Q, 0, sizeof(Q));
  memset(R, 0, sizeof(R));
  for (int i = (0); i <= (k); i++) {
    F[i] = (long long)a[i] * fac[k - i] % 1000000007 *
           power(2, (long long)i * (1 << idx) % (1000000007 - 1), 1000000007) %
           1000000007;
    G[i] = (long long)b[i] * fac[k - i] % 1000000007;
  }
  for (int i = (0); i <= (k); i++) {
    A[i].x = (double)(F[i] >> 15);
    B[i].x = (double)(F[i] & ((1 << 15) - 1));
    C[i].x = (double)(G[i] >> 15);
    D[i].x = (double)(G[i] & ((1 << 15) - 1));
  }
  FFT(A, all);
  FFT(B, all);
  FFT(C, all);
  FFT(D, all);
  for (int i = (0); i < (all); i++) {
    P[i] = A[i] * C[i];
    Q[i] = A[i] * D[i] + B[i] * C[i];
    R[i] = B[i] * D[i];
  }
  DFT(P, all);
  DFT(Q, all);
  DFT(R, all);
  memset(f, 0, sizeof(f));
  for (int i = (0); i <= (k); i++) {
    long long X = (long long)(P[i].x + 0.5) % 1000000007;
    long long Y = (long long)(Q[i].x + 0.5) % 1000000007;
    long long Z = (long long)(R[i].x + 0.5) % 1000000007;
    f[i] = ((X << 30) + (Y << 15) + Z) % 1000000007;
  }
  for (int i = (0); i <= (k); i++)
    f[i] = (long long)f[i] * inv[k] % 1000000007 * inv[k - i] % 1000000007;
}
int ans[65536];
void print(int* ans) {
  for (int i = (1); i <= (k); i++) printf("%d ", ans[i]);
  printf("\n");
}
int main() {
  scanf("%lld\n", &n);
  read(k);
  if (n > k) {
    printf("%d\n", 0);
    return 0;
  }
  fac[0] = 1;
  for (int i = (1); i < (65536); i++)
    fac[i] = (long long)fac[i - 1] * i % 1000000007;
  inv[65536 - 1] = power(fac[65536 - 1], 1000000007 - 2, 1000000007);
  for (int i = (65536 - 2); i >= (0); i--)
    inv[i] = (long long)inv[i + 1] * (i + 1) % 1000000007;
  pow2[0] = 1;
  for (int i = (1); i < (65536); i++) pow2[i] = pow2[i - 1] * 2 % 1000000007;
  for (l = 0, all = 1; all <= 2 * k; all <<= 1) l++;
  init(l);
  for (int i = (0); i < (all); i++)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  for (int i = (1); i <= (k); i++) f[0][i] = getC(k, i);
  int log = (int)log2(n);
  for (int i = (1); i <= (log); i++) mul(f[i], f[i - 1], f[i - 1], i - 1);
  memset(ans, 0, sizeof(ans));
  ans[0] = 1;
  for (int i = 0; i <= log; i++, n >>= 1)
    if (n & 1) mul(ans, ans, f[i], i);
  int res = 0;
  for (int i = (1); i <= (k); i++) (res += ans[i]) %= 1000000007;
  printf("%d\n", res);
  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 double PI = acos(-1);
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T alex(T x) {
  return (x > 0) ? x : -x;
}
template <class T>
void read(T& x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while ((ch < 48 || ch > 57) && ch != 45) ch = getchar();
  if (ch == 45) f = -1, ch = getchar();
  while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = getchar();
  x *= f;
}
long long n;
int k;
int f[17][65536];
int fac[65536], inv[65536], pow2[65536];
int power(int a, int b, int p) {
  int s = 1, w = a;
  while (b) {
    if (b & 1) s = (long long)s * w % p;
    w = (long long)w * w % p;
    b >>= 1;
  }
  return s;
}
struct CP {
  double x, y;
  CP() {}
  CP(double x, double y) : x(x), y(y) {}
  CP operator+(const CP& p) const { return CP(x + p.x, y + p.y); }
  CP operator-(const CP& p) const { return CP(x - p.x, y - p.y); }
  CP operator*(const CP& p) const {
    return CP(x * p.x - y * p.y, x * p.y + y * p.x);
  }
  CP operator*(const double& p) const { return CP(x * p, y * p); }
  CP operator/(const double& p) const { return CP(x / p, y / p); }
};
int getC(int n, int m) {
  return (long long)fac[n] * inv[m] % 1000000007 * inv[n - m] % 1000000007;
}
int l, r[65536], all;
CP A[65536], B[65536], C[65536], D[65536];
CP w[65536];
void print(CP* a) {
  for (int i = (0); i < (all); i++) printf("(%.3f %.3f)", a[i].x, a[i].y);
  printf("\n");
}
CP _w1[17][65536], _w2[17][65536];
void init(int l) {
  for (int i = (0); i < (l); i++) {
    for (int k = (0); k <= (1 << i); k++)
      _w1[i][k] = CP(cos(PI / (1 << i) * k), sin(PI / (1 << i) * k));
    for (int k = (0); k <= (1 << i); k++)
      _w2[i][k] = CP(cos(PI / (1 << i) * k), -sin(PI / (1 << i) * k));
  }
}
void FFT(CP* a, int n) {
  for (int i = (0); i < (n); i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1, z = 0; i < n; i <<= 1, z++) {
    for (int j = 0, del = i << 1; j < n; j += del) {
      for (int k = (0); k < (i); k++) {
        register CP x = a[j + k], y = _w1[z][k] * a[j + k + i];
        a[j + k] = x + y;
        a[j + k + i] = x - y;
      }
    }
  }
}
void DFT(CP* a, int n) {
  for (int i = (0); i < (n); i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1, z = 0; i < n; i <<= 1, z++) {
    for (int j = 0, del = i << 1; j < n; j += del) {
      for (int k = (0); k < (i); k++) {
        register CP x = a[j + k], y = _w2[z][k] * a[j + k + i];
        a[j + k] = x + y, a[j + k + i] = x - y;
      }
    }
  }
  for (int i = (0); i < (n); i++) a[i] = a[i] / n;
}
int F[65536], G[65536];
CP P[65536], Q[65536], R[65536];
void mul(int* f, int* a, int* b, int idx) {
  memset(A, 0, sizeof(A));
  memset(B, 0, sizeof(B));
  memset(C, 0, sizeof(C));
  memset(D, 0, sizeof(D));
  memset(P, 0, sizeof(P));
  memset(Q, 0, sizeof(Q));
  memset(R, 0, sizeof(R));
  for (int i = (0); i <= (k); i++) {
    F[i] = (long long)a[i] * fac[k - i] % 1000000007 *
           power(2, (long long)i * (1 << idx) % (1000000007 - 1), 1000000007) %
           1000000007;
    G[i] = (long long)b[i] * fac[k - i] % 1000000007;
  }
  for (int i = (0); i <= (k); i++) {
    A[i].x = (double)(F[i] >> 15);
    B[i].x = (double)(F[i] & ((1 << 15) - 1));
    C[i].x = (double)(G[i] >> 15);
    D[i].x = (double)(G[i] & ((1 << 15) - 1));
  }
  FFT(A, all);
  FFT(B, all);
  FFT(C, all);
  FFT(D, all);
  for (int i = (0); i < (all); i++) {
    P[i] = A[i] * C[i];
    Q[i] = A[i] * D[i] + B[i] * C[i];
    R[i] = B[i] * D[i];
  }
  DFT(P, all);
  DFT(Q, all);
  DFT(R, all);
  memset(f, 0, sizeof(f));
  for (int i = (0); i <= (k); i++) {
    long long X = (long long)(P[i].x + 0.5) % 1000000007;
    long long Y = (long long)(Q[i].x + 0.5) % 1000000007;
    long long Z = (long long)(R[i].x + 0.5) % 1000000007;
    f[i] = ((X << 30) + (Y << 15) + Z) % 1000000007;
  }
  for (int i = (0); i <= (k); i++)
    f[i] = (long long)f[i] * inv[k] % 1000000007 * inv[k - i] % 1000000007;
}
int ans[65536];
void print(int* ans) {
  for (int i = (1); i <= (k); i++) printf("%d ", ans[i]);
  printf("\n");
}
int main() {
  scanf("%lld\n", &n);
  read(k);
  if (n > k) {
    printf("%d\n", 0);
    return 0;
  }
  fac[0] = 1;
  for (int i = (1); i < (65536); i++)
    fac[i] = (long long)fac[i - 1] * i % 1000000007;
  inv[65536 - 1] = power(fac[65536 - 1], 1000000007 - 2, 1000000007);
  for (int i = (65536 - 2); i >= (0); i--)
    inv[i] = (long long)inv[i + 1] * (i + 1) % 1000000007;
  pow2[0] = 1;
  for (int i = (1); i < (65536); i++) pow2[i] = pow2[i - 1] * 2 % 1000000007;
  for (l = 0, all = 1; all <= 2 * k; all <<= 1) l++;
  init(l);
  for (int i = (0); i < (all); i++)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  for (int i = (1); i <= (k); i++) f[0][i] = getC(k, i);
  int log = (int)log2(n);
  for (int i = (1); i <= (log); i++) mul(f[i], f[i - 1], f[i - 1], i - 1);
  memset(ans, 0, sizeof(ans));
  ans[0] = 1;
  for (int i = 0; i <= log; i++, n >>= 1)
    if (n & 1) mul(ans, ans, f[i], i);
  int res = 0;
  for (int i = (1); i <= (k); i++) (res += ans[i]) %= 1000000007;
  printf("%d\n", res);
  return 0;
}

```