#include <bits/stdc++.h>
using namespace std;
const long double Pi = acos(-1);
long long n;
int k, w;
int fac[800005], inv[800005];
int Ans[800005], F[800005], G[800005];
int ksm(int a, int k) {
  if (!k) return 1;
  int p = ksm(a, k / 2);
  if (k & 1) return 1ll * a * p % 1000000007 * p % 1000000007;
  return 1ll * p * p % 1000000007;
}
struct cpx {
  long double r, i;
  cpx() {}
  cpx(long double a, long double b) { r = a, i = b; }
  cpx operator+(cpx b) { return cpx(r + b.r, i + b.i); }
  cpx operator-(cpx b) { return cpx(r - b.r, i - b.i); }
  cpx operator*(cpx b) { return cpx(r * b.r - i * b.i, r * b.i + i * b.r); }
  cpx operator/(long double a) { return cpx(r / a, i / a); }
  cpx operator*=(cpx b) { return *this = *this * b; }
  cpx operator/=(long double a) { return *this = cpx(r / a, i / a); }
  cpx operator!() { return cpx(r, -i); }
} K1[800005], B1[800005], K2[800005], B2[800005], P1[800005], Q1[800005],
    P2[800005], Q2[800005];
void Init1(int z) {
  for (int i = 0; i < w; i++) P1[i] = P2[i] = cpx(0, 0);
  for (int i = 0; i <= k; i++) {
    F[i] = 1ll * Ans[i] * inv[i] % 1000000007 * ksm(2, z * i) % 1000000007;
    G[i] = 1ll * Ans[i] * inv[i] % 1000000007;
    P1[i].r = F[i] / 31622;
    P1[i].i = F[i] % 31622;
    P2[i].r = G[i] / 31622;
    P2[i].i = G[i] % 31622;
  }
}
void Init2() {
  for (int i = 0; i < w; i++) P1[i] = P2[i] = cpx(0, 0);
  for (int i = 1; i <= k; i++) {
    F[i] = 1ll * Ans[i] * ksm(2, i) % 1000000007 * inv[i] % 1000000007;
    G[i] = inv[i];
    P1[i].r = F[i] / 31622;
    P1[i].i = F[i] % 31622;
    P2[i].r = G[i] / 31622;
    P2[i].i = G[i] % 31622;
  }
}
void DFT(cpx *A, int f) {
  for (int i = 1, j = 0; i < w; i++) {
    for (int d = w >> 1; j ^= d, ~j & d; d >>= 1)
      ;
    if (i < j) swap(A[i], A[j]);
  }
  for (int i = 1; i < w; i <<= 1) {
    cpx wn(cos(Pi / i), f * sin(Pi / i));
    for (int j = 0; j < w; j += i << 1) {
      int k = i + j;
      cpx w1(1, 0);
      for (int l = 0; l < i; l++) {
        cpx x = A[j + l], y = w1 * A[k + l];
        A[j + l] = x + y;
        A[k + l] = x - y;
        w1 *= wn;
      }
    }
  }
  if (f == -1)
    for (int i = 0; i < w; i++) A[i] /= w;
}
void FFT() {
  DFT(P1, 1), DFT(P2, 1);
  for (int i = 0; i < w; i++) {
    Q1[i] = !P1[(w - i) & (w - 1)];
    K1[i] = (P1[i] + Q1[i]) / 2;
    B1[i] = (P1[i] - Q1[i]) / 2;
    swap(B1[i].r, B1[i].i);
    B1[i].i = -B1[i].i;
    Q2[i] = !P2[(w - i) & (w - 1)];
    K2[i] = (P2[i] + Q2[i]) / 2;
    B2[i] = (P2[i] - Q2[i]) / 2;
    swap(B2[i].r, B2[i].i);
    B2[i].i = -B2[i].i;
  }
  for (int i = 0; i < w; i++) P1[i] = K1[i] * K2[i];
  DFT(P1, -1);
  for (int i = 0; i <= k; i++)
    Ans[i] =
        (long long)(P1[i].r + 0.5) * 31622 % 1000000007 * 31622 % 1000000007;
  for (int i = 0; i < w; i++) P1[i] = K1[i] * B2[i] + K2[i] * B1[i];
  DFT(P1, -1);
  for (int i = 0; i <= k; i++)
    Ans[i] =
        (Ans[i] + (long long)(P1[i].r + 0.5) * 31622 % 1000000007) % 1000000007;
  for (int i = 0; i < w; i++) P1[i] = B1[i] * B2[i];
  DFT(P1, -1);
  for (int i = 0; i <= k; i++)
    Ans[i] = (Ans[i] + (long long)(P1[i].r + 0.5)) % 1000000007;
  for (int i = 0; i <= k; i++) Ans[i] = 1ll * Ans[i] * fac[i] % 1000000007;
}
void Div(int z) {
  if (z == 1) {
    for (int i = 1; i <= k; i++) Ans[i] = 1;
    return;
  }
  Div(z / 2);
  Init1(z / 2);
  FFT();
  if (z & 1) {
    Init2();
    FFT();
  }
}
int main() {
  cin >> n >> k;
  if (n > k) {
    puts("0");
    return 0;
  }
  fac[0] = 1;
  for (int i = 1; i <= k; i++) fac[i] = 1ll * fac[i - 1] * i % 1000000007;
  inv[k] = ksm(fac[k], 1000000007 - 2);
  for (int i = k; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % 1000000007;
  for (w = 1; w <= 2 * k; w <<= 1)
    ;
  Div(n);
  int ans = 0;
  for (int i = 0; i <= k; i++) {
    ans = (ans + 1ll * Ans[i] * fac[k] % 1000000007 * inv[i] % 1000000007 *
                     inv[k - i] % 1000000007) %
          1000000007;
  }
  printf("%d\n", ans);
}

### Prompt

Please create a solution in CPP 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 long double Pi = acos(-1);
long long n;
int k, w;
int fac[800005], inv[800005];
int Ans[800005], F[800005], G[800005];
int ksm(int a, int k) {
  if (!k) return 1;
  int p = ksm(a, k / 2);
  if (k & 1) return 1ll * a * p % 1000000007 * p % 1000000007;
  return 1ll * p * p % 1000000007;
}
struct cpx {
  long double r, i;
  cpx() {}
  cpx(long double a, long double b) { r = a, i = b; }
  cpx operator+(cpx b) { return cpx(r + b.r, i + b.i); }
  cpx operator-(cpx b) { return cpx(r - b.r, i - b.i); }
  cpx operator*(cpx b) { return cpx(r * b.r - i * b.i, r * b.i + i * b.r); }
  cpx operator/(long double a) { return cpx(r / a, i / a); }
  cpx operator*=(cpx b) { return *this = *this * b; }
  cpx operator/=(long double a) { return *this = cpx(r / a, i / a); }
  cpx operator!() { return cpx(r, -i); }
} K1[800005], B1[800005], K2[800005], B2[800005], P1[800005], Q1[800005],
    P2[800005], Q2[800005];
void Init1(int z) {
  for (int i = 0; i < w; i++) P1[i] = P2[i] = cpx(0, 0);
  for (int i = 0; i <= k; i++) {
    F[i] = 1ll * Ans[i] * inv[i] % 1000000007 * ksm(2, z * i) % 1000000007;
    G[i] = 1ll * Ans[i] * inv[i] % 1000000007;
    P1[i].r = F[i] / 31622;
    P1[i].i = F[i] % 31622;
    P2[i].r = G[i] / 31622;
    P2[i].i = G[i] % 31622;
  }
}
void Init2() {
  for (int i = 0; i < w; i++) P1[i] = P2[i] = cpx(0, 0);
  for (int i = 1; i <= k; i++) {
    F[i] = 1ll * Ans[i] * ksm(2, i) % 1000000007 * inv[i] % 1000000007;
    G[i] = inv[i];
    P1[i].r = F[i] / 31622;
    P1[i].i = F[i] % 31622;
    P2[i].r = G[i] / 31622;
    P2[i].i = G[i] % 31622;
  }
}
void DFT(cpx *A, int f) {
  for (int i = 1, j = 0; i < w; i++) {
    for (int d = w >> 1; j ^= d, ~j & d; d >>= 1)
      ;
    if (i < j) swap(A[i], A[j]);
  }
  for (int i = 1; i < w; i <<= 1) {
    cpx wn(cos(Pi / i), f * sin(Pi / i));
    for (int j = 0; j < w; j += i << 1) {
      int k = i + j;
      cpx w1(1, 0);
      for (int l = 0; l < i; l++) {
        cpx x = A[j + l], y = w1 * A[k + l];
        A[j + l] = x + y;
        A[k + l] = x - y;
        w1 *= wn;
      }
    }
  }
  if (f == -1)
    for (int i = 0; i < w; i++) A[i] /= w;
}
void FFT() {
  DFT(P1, 1), DFT(P2, 1);
  for (int i = 0; i < w; i++) {
    Q1[i] = !P1[(w - i) & (w - 1)];
    K1[i] = (P1[i] + Q1[i]) / 2;
    B1[i] = (P1[i] - Q1[i]) / 2;
    swap(B1[i].r, B1[i].i);
    B1[i].i = -B1[i].i;
    Q2[i] = !P2[(w - i) & (w - 1)];
    K2[i] = (P2[i] + Q2[i]) / 2;
    B2[i] = (P2[i] - Q2[i]) / 2;
    swap(B2[i].r, B2[i].i);
    B2[i].i = -B2[i].i;
  }
  for (int i = 0; i < w; i++) P1[i] = K1[i] * K2[i];
  DFT(P1, -1);
  for (int i = 0; i <= k; i++)
    Ans[i] =
        (long long)(P1[i].r + 0.5) * 31622 % 1000000007 * 31622 % 1000000007;
  for (int i = 0; i < w; i++) P1[i] = K1[i] * B2[i] + K2[i] * B1[i];
  DFT(P1, -1);
  for (int i = 0; i <= k; i++)
    Ans[i] =
        (Ans[i] + (long long)(P1[i].r + 0.5) * 31622 % 1000000007) % 1000000007;
  for (int i = 0; i < w; i++) P1[i] = B1[i] * B2[i];
  DFT(P1, -1);
  for (int i = 0; i <= k; i++)
    Ans[i] = (Ans[i] + (long long)(P1[i].r + 0.5)) % 1000000007;
  for (int i = 0; i <= k; i++) Ans[i] = 1ll * Ans[i] * fac[i] % 1000000007;
}
void Div(int z) {
  if (z == 1) {
    for (int i = 1; i <= k; i++) Ans[i] = 1;
    return;
  }
  Div(z / 2);
  Init1(z / 2);
  FFT();
  if (z & 1) {
    Init2();
    FFT();
  }
}
int main() {
  cin >> n >> k;
  if (n > k) {
    puts("0");
    return 0;
  }
  fac[0] = 1;
  for (int i = 1; i <= k; i++) fac[i] = 1ll * fac[i - 1] * i % 1000000007;
  inv[k] = ksm(fac[k], 1000000007 - 2);
  for (int i = k; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % 1000000007;
  for (w = 1; w <= 2 * k; w <<= 1)
    ;
  Div(n);
  int ans = 0;
  for (int i = 0; i <= k; i++) {
    ans = (ans + 1ll * Ans[i] * fac[k] % 1000000007 * inv[i] % 1000000007 *
                     inv[k - i] % 1000000007) %
          1000000007;
  }
  printf("%d\n", ans);
}

```