#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
const int maxn = 200000;
int tmp[maxn], ww[maxn];
int fac[maxn], revfac[maxn];
int A[maxn], B[maxn];
int Inv[5][5];
int pa[maxn], pb[maxn], pc[maxn][5];
int mypow(int x, int y, int mod) {
  int sum = 1;
  for (; y; y >>= 1) {
    if (y & 1) sum = 1LL * sum * x % mod;
    x = 1LL * x * x % mod;
  }
  return sum;
}
const int magic[3] = {1004535809, 998244353, 104857601};
struct Unknown {
  int wn[25], P, G;
  void set(int x, int y) {
    P = x, G = y;
    for (int i = 1; i <= 23; i++) wn[i] = mypow(G, (P - 1) / (1 << i), P);
  }
  void change(int* y, int len) {
    for (int i = 1, j = len / 2; i < len - 1; i++) {
      if (i < j) swap(y[i], y[j]);
      int k = len / 2;
      for (; j >= k; j -= k, k /= 2)
        ;
      j += k;
    }
  }
  void NTT(int* y, int len, int on) {
    change(y, len);
    for (int h = 2, id = 1; h <= len; h <<= 1, ++id) {
      ww[0] = 1;
      for (int i = 1; i < (h >> 1); i++) ww[i] = 1LL * ww[i - 1] * wn[id] % P;
      for (int j = 0; j < len; j += h)
        for (int k = j; k < j + (h >> 1); k++) {
          int u = y[k], t = 1LL * y[k + (h >> 1)] * ww[k - j] % P;
          y[k] = (u + t) % P, y[k + (h >> 1)] = (u - t + P) % P;
        }
    }
    if (on == -1) {
      for (int i = 1; i < len / 2; i++) swap(y[i], y[len - i]);
      int inv = mypow(len, P - 2, P);
      for (int i = 0; i < len; i++) y[i] = 1LL * y[i] * inv % P;
    }
  }
  void mul(int* A, int* B, int len) {
    NTT(A, len, 1);
    NTT(B, len, 1);
    for (int i = 0; i < len; i++) A[i] = 1LL * A[i] * B[i] % P;
    NTT(A, len, -1);
  }
  void get_rev(int* A, int* rev, int t) {
    if (t == 1) {
      rev[0] = mypow(A[0], P - 2, P);
      return;
    }
    get_rev(A, rev, (t + 1) >> 1);
    int len = 1;
    while (len <= 2 * t + 1) len <<= 1;
    for (int i = 0; i < len; i++) tmp[i] = A[i];
    for (int i = t; i < len; i++) tmp[i] = 0;
    NTT(tmp, len, 1);
    NTT(rev, len, 1);
    for (int i = 0; i < len; i++)
      rev[i] = (2LL - 1LL * tmp[i] * rev[i] % P + P) % P * rev[i] % P;
    NTT(rev, len, -1);
    for (int i = t; i < len; i++) rev[i] = 0;
  }
};
Unknown ntt[3];
int CRT(int* a) {
  int x[3];
  for (int i = 0; i < 3; i++) {
    x[i] = a[i];
    for (int j = 0; j < i; j++) {
      int t = (x[i] - x[j] + magic[i]) % magic[i];
      if (t < 0) t += magic[i];
      x[i] = 1LL * t * Inv[j][i] % magic[i];
    }
  }
  int sum = 1, ret = x[0] % Mod;
  for (int i = 1; i < 3; i++) {
    sum = 1LL * sum * magic[i - 1] % Mod;
    ret += 1LL * x[i] * sum % Mod;
    if (ret >= Mod) ret -= Mod;
  }
  return ret;
}
void multiply(int* a, int* b, int len, long long right) {
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < len; j++)
      pa[j] = 1LL * a[j] * revfac[j] % Mod *
              mypow(2, right % (Mod - 1) * j % (Mod - 1), Mod) % Mod,
      pb[j] = 1LL * b[j] * revfac[j] % Mod;
    ntt[i].mul(pa, pb, len);
    for (int j = 0; j < len; j++) pc[j][i] = pa[j];
  }
  for (int i = 0; i < len; i++) a[i] = 1ll * CRT(pc[i]) * fac[i] % Mod;
}
void Prepare(int k) {
  for (int i = 0; i < 3; i++) ntt[i].set(magic[i], 3);
  for (int i = 0; i < 3; i++)
    for (int j = i + 1; j < 3; j++)
      Inv[i][j] = mypow(magic[i], magic[j] - 2, magic[j]);
  fac[0] = revfac[0] = 1;
  for (int i = 1; i <= k; i++)
    fac[i] = 1LL * fac[i - 1] * i % Mod,
    revfac[i] = mypow(fac[i], Mod - 2, Mod);
}
int main() {
  long long n;
  int k;
  scanf("%I64d %d", &n, &k);
  if (n > k)
    printf("0\n");
  else {
    Prepare(k);
    int len = 1;
    while (len <= 2 * (k + 1)) len <<= 1;
    A[0] = 0;
    for (int i = 1; i <= k; i++) A[i] = 1;
    B[0] = 1;
    long long x = 0, y = 1;
    for (; n; n >>= 1) {
      if (n & 1) {
        multiply(B, A, len, y);
        x += y;
      }
      multiply(A, A, len, y);
      y += y;
    }
    int Ans = 0;
    for (int i = 1; i <= k; i++)
      Ans = (Ans + 1LL * B[i] * fac[k] % Mod * revfac[i] % Mod * revfac[k - i] %
                       Mod) %
            Mod;
    printf("%d\n", Ans);
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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 int Mod = 1e9 + 7;
const int maxn = 200000;
int tmp[maxn], ww[maxn];
int fac[maxn], revfac[maxn];
int A[maxn], B[maxn];
int Inv[5][5];
int pa[maxn], pb[maxn], pc[maxn][5];
int mypow(int x, int y, int mod) {
  int sum = 1;
  for (; y; y >>= 1) {
    if (y & 1) sum = 1LL * sum * x % mod;
    x = 1LL * x * x % mod;
  }
  return sum;
}
const int magic[3] = {1004535809, 998244353, 104857601};
struct Unknown {
  int wn[25], P, G;
  void set(int x, int y) {
    P = x, G = y;
    for (int i = 1; i <= 23; i++) wn[i] = mypow(G, (P - 1) / (1 << i), P);
  }
  void change(int* y, int len) {
    for (int i = 1, j = len / 2; i < len - 1; i++) {
      if (i < j) swap(y[i], y[j]);
      int k = len / 2;
      for (; j >= k; j -= k, k /= 2)
        ;
      j += k;
    }
  }
  void NTT(int* y, int len, int on) {
    change(y, len);
    for (int h = 2, id = 1; h <= len; h <<= 1, ++id) {
      ww[0] = 1;
      for (int i = 1; i < (h >> 1); i++) ww[i] = 1LL * ww[i - 1] * wn[id] % P;
      for (int j = 0; j < len; j += h)
        for (int k = j; k < j + (h >> 1); k++) {
          int u = y[k], t = 1LL * y[k + (h >> 1)] * ww[k - j] % P;
          y[k] = (u + t) % P, y[k + (h >> 1)] = (u - t + P) % P;
        }
    }
    if (on == -1) {
      for (int i = 1; i < len / 2; i++) swap(y[i], y[len - i]);
      int inv = mypow(len, P - 2, P);
      for (int i = 0; i < len; i++) y[i] = 1LL * y[i] * inv % P;
    }
  }
  void mul(int* A, int* B, int len) {
    NTT(A, len, 1);
    NTT(B, len, 1);
    for (int i = 0; i < len; i++) A[i] = 1LL * A[i] * B[i] % P;
    NTT(A, len, -1);
  }
  void get_rev(int* A, int* rev, int t) {
    if (t == 1) {
      rev[0] = mypow(A[0], P - 2, P);
      return;
    }
    get_rev(A, rev, (t + 1) >> 1);
    int len = 1;
    while (len <= 2 * t + 1) len <<= 1;
    for (int i = 0; i < len; i++) tmp[i] = A[i];
    for (int i = t; i < len; i++) tmp[i] = 0;
    NTT(tmp, len, 1);
    NTT(rev, len, 1);
    for (int i = 0; i < len; i++)
      rev[i] = (2LL - 1LL * tmp[i] * rev[i] % P + P) % P * rev[i] % P;
    NTT(rev, len, -1);
    for (int i = t; i < len; i++) rev[i] = 0;
  }
};
Unknown ntt[3];
int CRT(int* a) {
  int x[3];
  for (int i = 0; i < 3; i++) {
    x[i] = a[i];
    for (int j = 0; j < i; j++) {
      int t = (x[i] - x[j] + magic[i]) % magic[i];
      if (t < 0) t += magic[i];
      x[i] = 1LL * t * Inv[j][i] % magic[i];
    }
  }
  int sum = 1, ret = x[0] % Mod;
  for (int i = 1; i < 3; i++) {
    sum = 1LL * sum * magic[i - 1] % Mod;
    ret += 1LL * x[i] * sum % Mod;
    if (ret >= Mod) ret -= Mod;
  }
  return ret;
}
void multiply(int* a, int* b, int len, long long right) {
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < len; j++)
      pa[j] = 1LL * a[j] * revfac[j] % Mod *
              mypow(2, right % (Mod - 1) * j % (Mod - 1), Mod) % Mod,
      pb[j] = 1LL * b[j] * revfac[j] % Mod;
    ntt[i].mul(pa, pb, len);
    for (int j = 0; j < len; j++) pc[j][i] = pa[j];
  }
  for (int i = 0; i < len; i++) a[i] = 1ll * CRT(pc[i]) * fac[i] % Mod;
}
void Prepare(int k) {
  for (int i = 0; i < 3; i++) ntt[i].set(magic[i], 3);
  for (int i = 0; i < 3; i++)
    for (int j = i + 1; j < 3; j++)
      Inv[i][j] = mypow(magic[i], magic[j] - 2, magic[j]);
  fac[0] = revfac[0] = 1;
  for (int i = 1; i <= k; i++)
    fac[i] = 1LL * fac[i - 1] * i % Mod,
    revfac[i] = mypow(fac[i], Mod - 2, Mod);
}
int main() {
  long long n;
  int k;
  scanf("%I64d %d", &n, &k);
  if (n > k)
    printf("0\n");
  else {
    Prepare(k);
    int len = 1;
    while (len <= 2 * (k + 1)) len <<= 1;
    A[0] = 0;
    for (int i = 1; i <= k; i++) A[i] = 1;
    B[0] = 1;
    long long x = 0, y = 1;
    for (; n; n >>= 1) {
      if (n & 1) {
        multiply(B, A, len, y);
        x += y;
      }
      multiply(A, A, len, y);
      y += y;
    }
    int Ans = 0;
    for (int i = 1; i <= k; i++)
      Ans = (Ans + 1LL * B[i] * fac[k] % Mod * revfac[i] % Mod * revfac[k - i] %
                       Mod) %
            Mod;
    printf("%d\n", Ans);
  }
  return 0;
}

```