#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
Z fact[35],ifac[35];
void init(int L){
    fact[0] = 1;
    rep(i,1,L) fact[i] = fact[i - 1] * i;
    ifac[L] = Z(1) / fact[L];
    per(i,L - 1,0) ifac[i] = ifac[i + 1] * (i + 1);
}

ll n;
int k;
const int L = 5;
const int aa[6] = {0,3,5,7,17,19},bb[6] = {0,2,11,13,23,29};
const Z ia[6] = {0,333333336,400000003,142857144,352941179,157894738},ib[6] = {0,500000004,818181824,153846155,739130440,758620695};
int _buc[6][35];
const int A = 1526175,B = 1526096;

Z ret;
void updA(int val,int C){
    rep(i,1,L){
        int rk = 0;
        while(val % aa[i] == 0){
            val /= aa[i];
            rk++;
        }
        rep(_k,1,rk){
            _buc[i][_k] += C;
            if(C > 0 && _buc[i][_k] > 1) ret *= ia[i];
            if(C < 0 && _buc[i][_k]) ret *= aa[i];
        }
    }
}

void updB(int val,int C){
    rep(i,1,L){
        int rk = 0;
        while(val % bb[i] == 0){
            val /= bb[i];
            rk++;
        }
        rep(_k,1,rk){
            _buc[i][_k] += C;
            if(C > 0 && _buc[i][_k] > 1) ret *= ib[i];
            if(C < 0 && _buc[i][_k]) ret *= bb[i];
        }
    }
}

Z a[A + 5],b[B + 5];
Z sum[2 * B + 5][35];

Z result[35],f[35],g[35];
void calc(ll u){
    fill(result,result + k + 2,0);

    int l = 0,r = 0;
    ll cur = 0;
    int idx = 0;
    rep(i,0,2 * A){
        while(1ll * A * l < cur) l++;
        while((r + 1 < B || i < A) && 1ll * A * (r + 1) - cur <= u) r++;
        if(i == A) chkmin(r,B - 1);

        rep(j,0,k + 1){
            if(l > r){
                f[j] = 0;
                continue;
            }
            f[j] = sum[r][j];
            if(l) f[j] -= sum[l - 1][j];
        }
        g[0] = a[idx];
        rep(j,1,k + 1) g[j] = g[j - 1] * (-cur + j - 1);

/*        printf("i=%d [%d,%d]\n",i,l,r);
        rep(j,0,k + 1) printf("%d ",f[j].val());
        printf("\n");
        rep(j,0,k + 1) printf("%d ",g[j].val());
        printf("\n"); */

        rep(j,0,k + 1){
            f[j] *= ifac[j];
            g[j] *= ifac[j];
        }

        rep(p,0,k + 1){
            rep(q,0,k + 1 - p) result[p + q] += f[p] * g[q];
        }

        cur += B;
        idx -= B;
        while(idx < 0) idx += A;
    }

    reverse(result,result + k + 2);
    rep(i,0,k + 1) result[i] *= ifac[i] * fact[k + 1];
/*    printf("calc u=%lld\n",u);
    rep(i,0,k + 1) printf("%d ",result[i].val());
    printf("\n");*/
    cerr << clock() << endl;
}

int main(){
//    freopen("test.in","r",stdin);
    scanf("%lld%d",&n,&k);
    init(k + 1);
    ret = 1;
    rep(i,0,k - 1) updA(A + i,1);
    rep(i,0,A){
        updA(A + i + k,1);
        if(i) updA(A + i - 1,-1);
        a[i] = ret;
    }
    ret = 1;
    memset(_buc,0,sizeof(_buc));
    rep(i,0,k - 1) updB(B + i,1);
    rep(i,0,B){
        updB(B + i + k,1);
        if(i) updB(B + i - 1,-1);
        b[i] = ret;       
    }
//    rep(i,0,A) printf("%d ",a[i].val());
//    printf("\n");
//    rep(i,0,B) printf("%d ",b[i].val());
//    printf("\n");
    cerr << clock() << endl;

    int idx = 0;
    Z cur = 0;
    rep(i,0,2 * B){
        sum[i][0] = b[idx];
        rep(j,1,k + 1) sum[i][j] = sum[i][j - 1] * (cur + j - 1);        

        idx += A;
        while(idx >= B) idx -= B;
        cur += A;
    }
    rep(i,1,2 * B){
        rep(j,0,k + 1) sum[i][j] += sum[i - 1][j];
    }
    cerr << clock() << endl;

    calc(1ll * A * B - 1);
    Z answer = 0,prd;
    ll h = 0;
    while(h + 1ll * A * B - 1 <= n){
        prd = 1;
        rep(i,0,k + 1){
            answer += result[i] * prd;
            prd *= h + i;
        }
        h += 1ll * A * B;
    }
    if(h <= n){
        calc(n - h);
        prd = 1;
        rep(i,0,k + 1){
            answer += result[i] * prd;
            prd *= h + i;
        }
    }
    printf("%d\n",answer.val());
/*    Z answer = 0,prd;
    rep(i,1,n){
        prd = 1;
        rep(j,0,k) prd *= i + j;
        answer += prd * a[i % A] * b[i % B];
    }
    printf("%d\n",answer.val());*/
    return 0;
}