求 $a+b$，等价于求 $\sum_{i=1}^{a}i^0+\sum_{i=1}^{b}i^0$

发现这个问题太困难了，暴力做是 $O(a+b)$ 的，会超时。

考虑到指数很小，我们容易想到快速求自然数幂之和。

先考虑 $\sum_{i=1}^{n}i^k$ 的求法。

设 $f_k(n)=\sum_{i=1}^{n}i^k$，注意到：

$\begin{aligned} f_k(n)&=\sum_{i=1}^{n}i^k \\&=\sum_{i=0}^{n-1}(i+1)^k \\&=1+\sum_{i=1}^{n}(i+1)^k-(n+1)^k \end{aligned}$

故 $f_k(n)+(n+1)^k=1+\sum_{i=1}^{n}(i+1)^k$

发现还可以用二项式定理，继续简化：

$\begin{aligned} f_k(n)+(n+1)^k&=1+\sum_{i=1}^{n}(i+1)^k \\&=1+\sum_{i=1}^{n}\sum_{j=0}^{k}\begin{pmatrix}k\\j\end{pmatrix}i^j \\&=1+\sum_{j=0}^{k}\begin{pmatrix}k\\j\end{pmatrix}\sum_{i=1}^{n}i^j \\&=1+\sum_{i=0}^{k}\begin{pmatrix}k\\i\end{pmatrix}f_i(n) \\&=1+\sum_{i=0}^{k-2}\begin{pmatrix}k\\i\end{pmatrix}f_i(n)+f_k(n)+kf_{k-1}(n) \end{aligned}$

我们惊奇地发现 $f_k(n)$ 被消去了，实际上我们已经得到 $f_{k-1}(n)$ 的表达式：

$f_{k-1}(n)=\frac{(n+1)^k-1-\sum_{i=0}^{k-2}\begin{pmatrix}k\\i\end{pmatrix}f_i(n)}{k}$

同理可得：

$\begin{aligned} f_k(n)=\frac{(n+1)^{k+1}-1-\sum_{i=0}^{k-1}\begin{pmatrix}k+1\\i\end{pmatrix}f_i(n)}{k+1} \end{aligned}$

计算 $f_k(n)$ 需要 $0$~$k-1$ 的 $f(n)$ 值，$O(k^2)$ 暴力递推即可。

此时足以通过此题，但还不最优，我们思考还能怎么优化。

不关心具体式子，我们发现 $f_k$ 实际上是一个 $k+1$ 次多项式，所以我们可以拉格朗日插值来计算 $f_k(n)$ 的值。

然而这样做是 $O(k^2)$，但是由于我们可以任意选点，所以我们选一段连续的横坐标，即可做到 $O(klogk)$。

具体地，可以选择 $1$~$k+2$。

原式为：$\begin{aligned} f_k(n)=\sum_{i=1}^{k+2}f_k(i)\prod_{i\ne j}\frac{n-j}{i-j} \end{aligned}$

由于 $i\in[1,k+2]$，所以对其化简：

$\begin{aligned} f_k(n)&=\sum_{i=1}^{k+2}f_k(i)\prod_{i\ne j}\frac{n-j}{i-j} \\&=\sum_{i=1}^{k+2}f_k(i)\frac{\prod_{j=1}^{i-1}(n-j)\prod_{j=i+1}^{k+2}(n-j)}{(i-1)!(k+2-i)!(-1)^{k+2-i}} \end{aligned}$

$O(k)$ 预处理阶乘、阶乘逆元，$(n-j)$ 的前缀积、后缀积，$O(klogk)$ 预处理 $1$~$k+2$ 内的 $f_k(i)$ 即可实现。

时间复杂度 $O(klogk)$，轻松通过此题。

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
const int N=1e6+10,mod=1e9+7;
int f[N],fac[N],infac[N],pre[N],suf[N],a,b,n;
int qpow(int a,int b){int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod,b>>=1;}return res;}
int cal(int k){
    fac[0]=1;FOR(i,1,k+2) fac[i]=1ll*fac[i-1]*i%mod;
    infac[k+2]=qpow(fac[k+2],mod-2);ROF(i,k+1,0) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    FOR(i,1,k+2) f[i]=(f[i-1]+qpow(i,k))%mod;
    pre[0]=1,suf[k+3]=1;
    FOR(i,1,k+2) pre[i]=1ll*pre[i-1]*(n-i)%mod;
    ROF(i,k+2,1) suf[i]=1ll*suf[i+1]*(n-i)%mod;
    if(n<=k+2){return f[n];}
    int ans=0;
    FOR(i,1,k+2){
        int res=1ll*pre[i-1]*suf[i+1]%mod;
        int tmp=1ll*infac[i-1]*((k+2-i)&1?-1ll:1ll)*infac[k+2-i]%mod;
        int tmp2=1ll*res*f[i]%mod*((tmp+mod)%mod)%mod;
        ans=(ans+tmp2)%mod;
    }
    return ans; 
}
int main(){
    a=rd,b=rd;int ans=0;
    n=a,ans+=cal(0),n=b,ans+=cal(0);
    printf("%d\n",ans);
    return 0;
}