Description：

求数列 $b_n=n^ka^n$ 的前 $n$ 项和 $T_n \ mod \ \left( 10^9+7 \right)$ 。

$1\leqslant n\leqslant 10^{18},1\leqslant k\leqslant 2000$

Solution：

发现 $n$ 很大 $k$ 很小，说明复杂度瓶颈在 $k$ 上，先错位相减，得： $$ \begin{align} (a-1)&T_n(k)=n^ka^{n+1}-a-\sum_{i=2}^n[i^k-(i-1)^k]a^i\\ \because &x^k=[(x-1)+1]^k=\sum_{i=0}^kC^k_i(x-1)^i\\ \therefore &(a-1)T_n(k)=n^ka^{n+1}-a-\sum_{i=2}^n[\sum_{j=0}^{k-1}C^k_j(i-1)^j]a^i\\ &(a-1)T_n(k)=n^ka^{n+1}-a-\sum_{j=0}^{k-1}C^k_j\sum_{i=2}^n(i-1)^ja^i\\ &(a-1)T_n(k)=n^ka^{n+1}-a-\sum_{j=0}^{k-1}C^k_ja\sum_{i=1}^{n - 1}i^ja^i\\ &(a-1)T_n(k)=n^ka^{n+1}-a-a\sum_{j=0}^{k-1}C^k_j(T_n(j)-n^ja^n) \end{align} $$

特别的： $$ T_n(0)=\sum_{i=1}^na^i=a\frac{a^n-1}{a-1} $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 1000000007

typedef long long ll;

ll n,a,k;

#define MAXK 2010

ll C[MAXK][MAXK];

inline ll power(ll a,ll b)

{

    a %= MOD; 

    ll res = 1;

    while(b > 0)

    {

        if(b & 1)res = res * a % MOD;

        a = a * a % MOD;

        b = b >> 1;

    }

    return res;

}

inline ll inv(ll a)

{

    return power(a,MOD - 2);

}

ll T[MAXK];

ll po[MAXK];

int main()

{

    scanf("%lld%lld%lld",&n,&a,&k);

    C[0][0] = 1;

    for(register ll i = 1;i <= k;++i)

    {

        C[i][0] = C[i][i] = 1;

        for(register ll j = 1;j < i;++j)

        {

            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;

        }

    }

    T[0] = a * (power(a,n) - 1 + MOD) % MOD * inv(a - 1) % MOD;

    po[0] = 1;

    for(register ll i = 1;i <= k;++i)po[i] = po[i - 1] * (n % MOD) % MOD;

    ll pan = power(a,n);

    for(register ll i = 1;i <= k;++i)

    {

        register ll ans = 0;

        for(ll j = 0;j <= i - 1;++j)

        {

            ans = (ans + C[i][j] * (T[j] - po[j] * pan % MOD + MOD) % MOD) % MOD;

        }

        T[i] = ((po[i] * pan % MOD * a % MOD) - a + MOD - (a * ans % MOD) + MOD) % MOD;

        T[i] = T[i] * inv(a - 1) % MOD;

    }

    cout << T[k] << endl;

    return 0;

}