求卡空间

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e7+10,P=1e9+7;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
ll fp(ll a,ll b=P-2){a%=P;b%=P-1;ll ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
struct Line{
    int k,b;
    friend Line operator*(Line x,ll y){
        return {(x.k*y%P+P)%P,(x.b*y%P+P)%P};
    }
    friend Line operator+(Line x,ll y){
        return {x.k,(x.b+y)%P};
    }
    friend Line operator+(Line x,Line y){
        return {(x.k+y.k)%P,(x.b+y.b)%P};
    }
}l[N];
ll n1,n2,a,K,tot;
int pw[N],fc[N],inv[N],g[N],p[N];
bitset<N>vis;
ll C(ll n,ll m){if(n<m)return 0;return 1ll*fc[n]*inv[n-m]%P*inv[m]%P;}
ll La(int n,int k,int y[]){
    ll ans=0;p[0]=pw[n+1]=1;
    for(int i=1;i<=n;++i)p[i]=1ll*(k-i+P)%P*p[i-1]%P;
    for(int i=n;~i;--i)pw[i]=1ll*(k-i+P)%P*pw[i+1]%P;
    for(int i=1;i<=n;++i){
        ll k1=1ll*p[i-1]*pw[i+1]%P,k2;
        if((n-i)&1)k2=(-1ll*inv[i-1]*inv[n-i]%P+P)%P;
        else k2=1ll*inv[i-1]*inv[n-i]%P;
        ans=(ans+y[i]*k1%P*k2%P)%P;
    }
    return ans;
}
int main(){
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')n1=((n1<<3)+(n1<<1)+(c^48))%P,n2=((n2<<3)+(n2<<1)+(c^48))%(P-1),c=getchar();
    K=read();
    a=fp(2);ll ans=fp(n1,K);--n1;--n2;
    fc[0]=fc[1]=pw[1]=1;
    for(int i=2;i<N;++i){
        if(!vis[i])p[++tot]=i,pw[i]=fp(i,K);
        for(int j=1;j<=tot&&i*p[j]<N;++j){
            vis[i*p[j]]=1;
            pw[i*p[j]]=1ll*pw[i]*pw[p[j]]%P;
            if(i%p[j]==0)break;
        }
        fc[i]=1ll*fc[i-1]*i%P;
    }
    inv[N-1]=fp(fc[N-1]);
    for(int i=N-2;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%P;
    l[0]={1,0};Line s={0,0};ll inva=fp(a);
    for(int i=1;i<=K+1;++i)l[i]=l[i-1]*inva+pw[i];
    for(int i=0;i<=K+1;++i){
        Line at=l[K+1-i]*C(K+1,i);
        if(i&1)s=s+at*(-1);
        else s=s+at;
    }
    g[0]=(-s.b*fp(s.k)%P+P)%P;
    for(int i=1;i<=K+1;++i)g[i]=(1ll*l[i].k*g[0]%P+l[i].b)%P;
    printf("%lld\n",((fp(a,n2)*La(K+1,n1%P,g)%P-g[0]+P)%P*fp(2,n2)%P+ans)%P);
    return 0;
}