#include <bits/stdc++.h>
#define MOD 1000000007
inline int pw(int a,int b) {
    int as=1;
    while(b) {
        if(b&1) as=1ll*as*a%MOD;
        a=1ll*a*a%MOD;
        b>>=1;
    }
    return as;
}
inline int ni(int a) {
    return pw(a,MOD-2);
}
#define LL long long
LL N;int cf,K,su[34],k,ans,v[34],fa[34][34],C[34][34],f1[34],cc[34],ss[34][34],fq[34],
vi[34],vc[109],xx[34],q,iq[34];LL suu[34];
inline int fd(int x,int y) {
    int aq=0,zz=1;
    for(int i=0;i<=y+1;i++) {
        aq=(aq+1ll*zz*ss[y][i])%MOD;
        zz=1ll*x*zz%MOD;
    }
    return aq;
}
struct n2_t{
    int x,y,ss,v;
} tq[22394889];
struct n_t{
    int x,y,v;
};
std::vector<n_t> tx[33];
inline bool cmp(n2_t x,n2_t y) {
    return (x.x==y.x)?(x.ss<y.ss):(x.x<y.x);
}
void dfs(int n,LL x,LL y,int tp) {
    if(y>N) return;
    if(n==k+1) {
        tq[++cf]=(n2_t){x%MOD,y%MOD,((N-y)/x)%MOD,tp};
        return;
    }
    for(int i=0;i<tx[n].size();i++) {
        LL tt=y;
        while(tt%tx[n][i].x!=tx[n][i].y) tt+=x;
        dfs(n+1,x*tx[n][i].x,tt,1ll*tp*tx[n][i].v%MOD);
    }
}
void sv(int id,int a,int b) {
    //printf("%d %d %d\n",id,a,b);
    std::unordered_map<int,int> qq;
    int num=0,as=0;
    for(int i=b;i<q;i+=a) {
        qq[fa[id][i]]++;
        if(qq[fa[id][i]]>num) as=fa[id][i],num++;
    }
    for(int i=b;i<q;i+=a) {
        fa[id][i]=(fa[id][i]-as+MOD)%MOD;
    }
    if(as) tx[id].push_back((n_t){a,b,as});
    if(a==q) return;
    for(int i=0;i<su[id];i++) sv(id,a*su[id],b+i*a);
}
signed main(void) {
    scanf("%lld %d",&N,&K);
    //mod x = y : chu ???
    // ?????? 
    for(int i=0;i<=K+1;i++) {
        C[i][0]=1;
        for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    for(int i=2;i<=K;i++) {
        if(!v[i]) {
            su[++k]=i;
        }
        for(int j=i*2;j<=K;j+=i) v[j]=1;
    }
    for(int i=0;i<=K+1;i++) {
        //i+1 ci duo xiang shi
        int as=0;
        for(int j=0;j<=i+1;j++) {
            as=(as+pw(j,i))%MOD;
            fq[j]=as;
        }
        for(int j=0;j<=i+1;j++) {
            cc[0]=1;
            int az=fq[j],cf=0;
            for(int k=0;k<=i+1;k++) {
                if(j==k) continue;
                for(int l=cf+1;l>=1;l--) {
                    cc[l]=(cc[l-1]+1ll*cc[l]*(MOD-k))%MOD;
                }
                cf++;
                cc[0]=1ll*cc[0]*(MOD-k)%MOD;
                az=1ll*az*ni(j-k+MOD)%MOD;
            }
            for(int k=0;k<=cf;k++) {
                ss[i][k]=(ss[i][k]+1ll*cc[k]*az)%MOD;
            }
            memset(cc,0,sizeof(cc));
        }
    }
    for(int i=1;i<=k;i++) {
        q=1;
        while(q*su[i]<=K) {
            q*=su[i];
        }
        for(int j=0;j<q;j++) {
            int aq=0,ma=0;
            for(int k=0;k<=K;k++) {
                int x=k+((j==0)?q:j),ct=0;
                while(x%su[i]==0) {
                    x/=su[i];
                    ct++;
                }
                aq+=ct;
                ma=std::max(ma,ct);
            }
            fa[i][j]=pw(su[i],MOD-1-(aq-ma));
        }
        sv(i,1,0);
    }
    cc[0]=1;
    for(int j=0;j<=K;j++) {
        for(int k=j+1;k>=1;k--) {
            cc[k]=(cc[k-1]+1ll*cc[k]*j)%MOD;
        }
        cc[0]=0;
    }
    dfs(1,1,0,1);
    std::sort(tq+1,tq+cf+1,cmp);
    int la=0;
    for(int i=1;i<=cf;i++) {
        int la=i;
        while(la<cf&&tq[la].x==tq[la+1].x&&tq[la].ss==tq[la+1].ss) {
            la++;
        }
        int xx=tq[i].ss;
        int x=tq[i].x;
        int aq=1;
        for(int j=0;j<=K+1;j++) {
            f1[j]=1ll*aq*fd(xx,j)%MOD;
            aq=1ll*aq*x%MOD;
        }
        memset(iq,0,sizeof(iq));
        for(int j=0;j<=K+1;j++) {
            for(int k=j;k>=0;k--) {
                iq[j-k]=(iq[j-k]+1ll*f1[k]*C[j][k]%MOD*cc[j])%MOD;
            }
        }
        for(int j=i;j<=la;j++) {
            int y=tq[j].y;
            int ac=tq[j].v;
            for(int j=0;j<=K+1;j++) {
                suu[j]+=ac;
                ac=1ll*ac*y%MOD;
            }
        }
        for(int j=0;j<=K+1;j++) {
            ans=(ans+suu[j]%MOD*iq[j])%MOD;
            suu[j]=0;
        }
        i=la;
    }
    printf("%d",ans);
}