A - Character Encoding
思路 ：
隔板法就是在n个元素间的（n-1）个空中插入k-1个板，可以把n个元素分成k组的方法
普通隔板法
求方程 x+y+z=10的正整数解的个数。
添元素隔板法
求方程 x+y+z=10的非负整数解的个数。 那么 增加 3 即转化为 了普通隔板法
但是这个题呢 还有 < N 的限制 ，那么就需要去除掉 ，分出的块中 有 > = n 的情况 。
就会 有 一块 出现 > =n ,两块 > =n 等等。。 具体 需要根据总数来确定 ，要去除这些情况贡献的解
发现 如果 有某一块 > = n 那么就转化为了 先把n个 放到 某一块上 ，剩下的 总数 - n 再 进行 分为 m块的 分配，
计算式即为 。 某一块 * （剩下的 分到 m块上） 但是这样会多减去一些，因为 这些情况中包含了
有 两块 > = n 三块 > =n 等等 。所以 需要 加回来 两块的情况，
#include<bits/stdc++.h>
using namespace std;
#define maxn 234567
#define ll long long
#define mod 998244353
ll n,m,k,inv[maxn+10],A[maxn+10],ans,t;
ll qpow(ll a,ll b)
{
ll re=1;
while(b)
{
if(b%2)
re=(re*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return re;
}
void init()
{
A[0]=inv[0]=1;
for(int i=1; i<=maxn; i++)
{
A[i]=(A[i-1]*i)%mod;
inv[i]=qpow(A[i],mod-2)%mod;
}
}
ll C(ll a,ll b)
{
if(b<a)return 0;
return (A[b]*inv[a]%mod*inv[b-a])%mod;
}
int main()
{
init();
scanf("%lld",&t);
while(t--)
{
ans=0;
scanf("%lld%lld%lld",&n,&m,&k);
if(k==0)printf("1\n");
else if(k>m*(n-1))printf("0\n");
else if(k<n) printf("%lld\n",C(m-1,m+k-1));
else
{
ll x=-1;
ans=C(m-1,m+k-1);
for(int i=1; i<=m; i++)
{
ans=(ans+C(i,m)*x%mod*C(m-1,k+m-1-i*n)%mod+mod)%mod;
x*=-1;
}
printf("%lld\n",ans);
}
}
return 0;
}