题意在此就不再简述了，主要是提供另一种做法。
观察
通过观察样例解释一，不难猜想其符合杨辉三角，通过打表简单验证一下发现是正确的，具体的证明过程这里就不放了。
于是到此，你便获得了一个 \(O(\sum n)\)
的做法。
但本题只限制了 \(\sum m\)
的值，并没有限制 \(\sum
n\)，于是你只能通过 sub2，sub5，sub7，获得 \(35\) 分。
似乎优化是没有什么前途的，但实际上，我们可以通过推式子，将其转化为 \(O(\sum m)\) 的。
思路
我们不妨先写出前面 \(O(\sum n)\) 的式子。
\[ ans=\sum_{i=0}^{n-1} \begin{pmatrix} m-1+i\\ m-1\\ \end{pmatrix} k^{n-i}\\ \]
在下文中，为了方便，我们都先将 \(m\) 减少 \(1\)。
那么原式子就变成了：
\[ ans=\sum_{i=0}^{n-1} \begin{pmatrix} m+i\\ m\\ \end{pmatrix} k^{n-i}\\ \]
发现这个式子类似于 \(\sum\limits_{i=0}^{n-1}k_{i}a^{i}\)，不难想到利用类似于等比数列求和的方式来解决。
我们令：
\[ f(m)=\sum_{i=0}^{n-1}\begin{pmatrix}m+i\\m\\\end{pmatrix}k^{n-i} \]
两边同时乘以 \(k\)，得到：
\[ kf(m)=\sum_{i=0}^{n-1}\begin{pmatrix}m+i\\m\\\end{pmatrix}k^{n-i+1} \]
这两个式子相减，得到：
\[ (k-1)f(m)= k^{n+1}+ \sum_{i=0}^{n-2} \left( \begin{pmatrix} m+i+1\\ m\\ \end{pmatrix}- \begin{pmatrix} m+i\\ m\\ \end{pmatrix} \right) k^{n-i}- \begin{pmatrix} m+n-1\\ m\\ \end{pmatrix} k \]
中间的两个组合数相减是可以化简的，等于 \(\begin{pmatrix}m+i\\m-1\\\end{pmatrix}\)。
那么我们的 \(f(m)\)，也就等于：
\[ f(m)= \dfrac{ k^{n+1}+ \sum\limits_{i=0}^{n-2} \begin{pmatrix} m+i\\ m-1\\ \end{pmatrix} k^{n-i}- \begin{pmatrix} m+n-1\\ m\\ \end{pmatrix} k} {k-1}\\ \]
我们将中间的 \(\sum\limits_{i=0}^{n-2}\begin{pmatrix}m+i\\m-1\\\end{pmatrix}k^{n-i}\) 单独提出来考虑。
发现我们枚举的范围，从 \([0,n-1]\)
变成了 \([0,n-2]\)，同时组合数中，下面的数，也从
\(m\) 变成了 \(m-1\)。
那么我们不妨将原来的 \(f(m)\)
改写成如下形式：
\[ f(m)= \sum_{i=0}^{n-1-(M-m)} \begin{pmatrix} M+i\\ m\\ \end{pmatrix} k^{n-i}\\ \]
其中式子中的 \(M\) 表示的是输入的 \(m\) 的值减少 \(1\)，式子中的 \(m\) 则表示一个自变量。
重新推一下式子：
\[ \begin{aligned} f(m)=& \sum_{i=0}^{n-1-(M-m)} \begin{pmatrix} M+i\\ m\\ \end{pmatrix} k^{n-i}\\ kf(m)=& \sum_{i=0}^{n-1-(M-m)} \begin{pmatrix} M+i\\ m\\ \end{pmatrix} k^{n-i+1}\\ (k-1)f(m)=& \begin{pmatrix} M\\ m\\ \end{pmatrix} k^{n+1}+ \sum_{i=0}^{n-2-(M-m)} \left( \begin{pmatrix} M+i+1\\ m\\ \end{pmatrix}- \begin{pmatrix} M+i\\ m\\ \end{pmatrix} \right) k^{n-i}- \begin{pmatrix} m+n-1\\ m\\ \end{pmatrix} k^{1+(M-m)}\\ (k-1)f(m)=& \begin{pmatrix} M\\ m\\ \end{pmatrix} k^{n+1}+ \sum_{i=0}^{n-2-(M-m)} \begin{pmatrix} M+i\\ m-1\\ \end{pmatrix} k^{n-i}- \begin{pmatrix} m+n-1\\ m\\ \end{pmatrix} k^{1+(M-m)}\\ (k-1)f(m)=& \begin{pmatrix} M\\ m\\ \end{pmatrix} k^{n+1}+ f(m-1)- \begin{pmatrix} m+n-1\\ m\\ \end{pmatrix} k^{1+(M-m)}\\ f(m)=& \dfrac{ \begin{pmatrix} M\\ m\\ \end{pmatrix} k^{n+1}+ f(m-1)- \begin{pmatrix} m+n-1\\ m\\ \end{pmatrix} k^{1+(M-m)} } {k-1}\\ \end{aligned} \]
不难发现是一个递归的形式，\(f(0)=\sum\limits_{i=0}^{n-M-1}k^{n-i}=\sum\limits_{i=0}^{n}k^{i}-\sum\limits_{i=0}^{M}k^{i}\)，这个是可以通过两个等比数列求和公式在 \(O(1)\) 的时间内得到的。
于是，我们便将原来 \(O(n)\) 的式子，转化成了递归形式的 \(O(m)\) 的式子。
细节
首先，我们观察到 \(f(m)\)
的式子中，随着 \(m\) 的降低，\(\sum\limits_{i=0}^{n-1-(M-m)}\) 中的 \(n-1-(M-m)\) 是在不断减少的。
那么当 \(n-1-(M-m)\) 先减到 \(-1\) 的时候，也就是当 \(n\le M\)
的时候，这个式子就寄掉了，但是这个时候，我们又可以用最开始的式子了。
还有一处细节。
当 \(k=0\) 或者 \(k=1\)
的时候，我们推导出来的式子也不管用了。
这时候简单推一下，可以得出 \(O(1)\)
的计算公式，这个式子我就不推了。
最后，因为 \(\sum m\le 2\times 10^7\)，这是比较大的。我们要减少快速幂的使用，所以对于原先的递归式子，我们在实现的时候，写成迭代，这样在迭代求解的过程中，是可以不用到快速幂的。
代码
// Problem: P12405 「CZOI-R3」星光闪耀
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P12405
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=4e6+10;
const int mod=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
x=0;
bool f=false;
char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
read(x),read(y...);
}
int T,n,m,k,ans,fac[MAXN],inv[MAXN];
int C(int a,int b){
return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
signed main(){
read(T);
fac[0]=1;
for(int i=1;i<=4e6;i++) fac[i]=fac[i-1]*i%mod;
inv[4000000]=qpow(fac[4000000],mod-2);
for(int i=4e6-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
while(T--){
read(n,m,k);m--;
ans=0;
int invk=qpow(k,mod-2);
if(k==0) ans=0;
else if(k==1) ans=C(m+n,m+1);
else if(n<=m+1){
int z=qpow(k,n);
for(int i=0;i<=n-1;i++){
(ans+=C(m+i,i)*z%mod)%=mod;
z=z*invk%mod;
}
}
else{
int val1=qpow(k,n+1),val2=qpow(k-1,mod-2),val3=qpow(k,m);
ans=((val1-1+mod)%mod*val2%mod-(qpow(k,m+1)-1+mod)%mod*val2%mod+mod)%mod;
for(int i=1;i<=m;i++){
ans=(C(m,i)*val1%mod+ans-C(i+n-1,i)*val3%mod+mod)%mod*val2%mod;
val3=val3*invk%mod;
}
}
cout<<ans<<'\n';
}
return 0;
}