In computer science, a character is a letter, a digit, a punctuation mark or some other similar symbol. Since computers can only process numbers, number codes are used to represent characters, which is known as character encoding. A character encoding system establishes a bijection between the elements of an alphabet of a certain size n and integers from 0 to n−1. Some well known character encoding systems include American Standard Code for Information Interchange (ASCII), which has an alphabet size 128, and the extended ASCII, which has an alphabet size 256.

For example, in ASCII encoding system, the word 𝚠𝚍𝚢 is encoded as [119, 100, 121], while 𝚓𝚜𝚠 is encoded as [106, 115, 119]. It can be noticed that both 119+100+121=340 and 106+115+119=340, thus the sum of the encoded numbers of the two words are equal. In fact, there are in all 903 such words of length 3 in an encoding system of alphabet size 128 (in this example, ASCII). The problem is as follows: given an encoding system of alphabet size n where each character is encoded as a number between 0 and n−1 inclusive, how many different words of length m are there, such that the sum of the encoded numbers of all characters is equal to k?

Since the answer may be large, you only need to output it modulo 998244353.

#### 大致题意 📖

$x_1 + x_2 + x_3 + \cdots + x_m = k （0 <= x_i < n）$

#### 链接 🔗

「CodeForces 1198C」 Matching vs Independent Set

#### 题解 ❓

$ans = C^{m-1}_{m+x-1} + \sum_{i=1}^m C_m^1 * C_{m+k-n-1}^{m-1} * (-1)^i$

#### 代码

const ll N = 2e5+10;
const ll mod = 998244353;
struct
{
ll fac[N],inv[N],Finv[N];//分别代表逆元，阶乘，阶乘逆元;
void init()
{
fac[0] = 1ll, Finv[0]=1ll,inv[1]=1ll;
for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<N;i++)
{
fac[i]=fac[i-1]*i%mod;
Finv[i]=Finv[i-1]*inv[i]%mod;
}
}
ll C(ll n,ll m)
{
if(n<0||m<0||m>n) return 0;
return fac[n] * Finv[m] %mod * Finv[n-m] %mod;
}
}comb;
int main()
{
//    __IN;__OUT
ll T;RLL(T);
comb.init();
while(T--)
{
ll n,m,k;RLL3(n,m,k);
ll res = 0;
for(int i=0;i*n<=k;i++)
{
if(i&1) res=(res-comb.C(m,i)*comb.C(k-i*n+m-1,m-1) % mod + mod)%mod;
else res=(res+comb.C(m,i)*comb.C(k-i*n+m-1,m-1)%mod)%mod;
}
PLN(res);
}
return 0;
}