#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

using ll = long long;

const ll L = 2329089562800ll;

const int P = 1e9 + 7;

const int N = 30 + 5;
const int M = 3e6 + 10;

const int L1 = 831600;
const int L2 = 2800733;

const ll M1 = 2151514688401ll;
const ll M2 = 177574874400ll;

const int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
const int factor[] = { 16, 27, 25, 7, 11, 13, 17, 19, 23, 29 };

ll read() {
  ll x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
void add(int &a, int b) { (a += b) >= P ? a -= P : 1; }
void sub(int &a, int b) { (a -= b) < 0 ? a += P : 1; }
int sgn(int x) { return x & 1 ? P - 1 : 1; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }

int fac[N], inv[N], finv[N];
void init(int w) {
  fac[0] = inv[1] = finv[0] = 1;
  rep(i, 1, w) fac[i] = mul(fac[i - 1], i);
  rep(i, 2, w) inv[i] = P - mul(P / i, inv[P % i]);
  rep(i, 1, w) finv[i] = mul(finv[i - 1], inv[i]);
}

int C(int a, int b) {
  if (a < b || b < 0) return 0;
  return mul(fac[a], mul(finv[b], finv[a - b]));
}

ll gcd(ll a, ll b) {
  return __gcd(a, b);
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

struct lagrange {
  int len, y[N], pre[N], suf[N];
  int calc(ll x) {
    if (x <= len) return y[x];
    pre[0] = suf[len + 1] = 1;
    rep(i, 1, len) pre[i] = mul(pre[i - 1], (x - i) % P);
    drep(i, len, 1) suf[i] = mul(suf[i + 1], (x - i) % P);
    int res = 0;
    rep(i, 1, len) {
      int t = mul(pre[i - 1], suf[i + 1]);
      t = mul(mul(t, sgn(len - i)), mul(finv[i - 1], finv[len - i]));
      add(res, mul(y[i], t));
    }
    return res;
  }
} lag[N];

long long n, w;
int m, ans;

int coef[N], f[N][N], g[N][N], cf[N][N], cg[N][N], pw[N], c[N][N];

int pre[N][M];
pair <ll, int> r1[M], r2[M];

void prework() {
  rep(i, 0, 31) {
    lag[i].len = i + 2, lag[i].y[0] = !i;
    rep(j, 1, i + 2) {
      lag[i].y[j] = inc(lag[i].y[j - 1], qpow(j, i));
    }
  }
  w = (n - 1) / L;
  rep(i, 0, m) pw[i] = lag[i].calc(w);
  coef[0] = 1;
  rep(i, 0, m - 1) drep(j, i, 0) {
    add(coef[j + 1], coef[j]);
    coef[j] = mul(coef[j], i);
  }
  rep(a, 0, m) rep(b, 0, m) rep(c, 0, m) {
    if (a + b + c > m) break;
    int t = mul(coef[a + b + c], fac[a + b + c]);
    t = mul(mul(t, finv[a]), mul(finv[b], finv[c]));
    add(f[b][c], mul(t, mul(pw[a], qpow(L % P, a))));
    add(g[b][c], mul(t, qpow(mul(w % P, L % P), a)));
  }
  auto vp = [&](int x, int p) {
    int res = 0;
    while (!(x % p)) ++ res, x /= p;
    return res;
  } ;
  rep(i, 0, 9) rep(j, 1, factor[i]) {
    int sum = 0, mx = 0;
    rep(k, 0, m - 1) {
      sum += vp(j + k, prime[i]);
      mx = max(mx, vp(j + k, prime[i]));
    }
    c[i][j % factor[i]] = qpow(prime[i], sum - mx);
  }
  rep(i, 0, L1 - 1) {
    ll u = i * M1 % L;
    int v = 1;
    rep(j, 0, 4) v = mul(v, c[j][i % factor[j]]);
    r1[i] = make_pair(u, v);
  }
  rep(i, 0, L2 - 1) {
    ll u = i * M2 % L;
    int v = 1;
    rep(j, 5, 9) v = mul(v, c[j][i % factor[j]]);
    r2[i] = make_pair(u, v);
  }
  sort(r1, r1 + L1);
  sort(r2, r2 + L2);
  rep(i, 1, L2) {
    for (int j = 0, x = qpow(r2[i - 1].second, P - 2); j <= m; ++ j)  {
      pre[j][i] = inc(pre[j][i - 1], x);
      x = mul(x, r2[i - 1].first % P);
    }
  }
}

int main() {
  init(N - 1);
  n = read(), m = read() + 1;
  prework();
  for (int i = L1 - 1, j1 = 0, j2 = 0, j3 = 0; ~i; -- i) {
    while (j1 < L2 && r1[i].first + r2[j1].first < L && w * L + r1[i].first + r2[j1].first <= n) ++ j1;
    while (j2 < L2 && r1[i].first + r2[j2].first < L) ++ j2;
    j3 = max(j3, j2);
    while (j3 < L2 && w * L + r1[i].first + r2[j3].first - L <= n) ++ j3;
    for (int u = 0, x = qpow(r1[i].second, P - 2), y = x; u <= m; ++ u) {
      rep(v, 0, m - u) {
        auto ask = [&](int l, int r) { return dec(pre[v][r], pre[v][l]); } ;
        add(cf[u][v], inc(mul(x, ask(0, j2)), mul(y, ask(j2, L2))));
        add(cg[u][v], inc(mul(x, ask(j1, j2)), mul(y, ask(j3, L2))));
      }
      x = mul(x, r1[i].first % P);
      y = mul(y, ((r1[i].first - L) % P + P) % P);
    }
  }
  rep(u, 0, m) rep(v, 0, m) {
    add(ans, mul(f[u][v], cf[u][v]));
    sub(ans, mul(g[u][v], cg[u][v]));
  }
  printf("%d\n", ans);
  return 0;
}