U277132 N数之和

## 征求解法！！ 目前可做到 $60\%$ 的数据

给你三个整数 $n$，$k$ 和 $S$， 请问 有多少个长度为 $n$ 序列 $A$，满足 - $\forall i \in [1,n]$，$0\le a_i \le k$。 - $\sum\limits_{i=1}^{n} a_i=S$ 答案对 $998244353$ 取模。

一行三个整数 $n$，$k$，$S$。

一行一个整数，表示答案。

样例解释： $A$ 可以是：$\{0,0,2\}$，$\{0,2,0\}$，$\{2,0,0\}$，$\{0,1,1\}$，$\{1,1,0\}$，$\{1,0,1\}$ 共 $6$ 种。 数据范围： 对于 $20\%$ 的数据：$n=2$ 对于 $30\%$ 的数据：$n \le 3$，$k \le 2500$ 对于 $50\%$ 的数据：$n \le 3$，$k \le 10^6$ 对于 $60\%$ 的数据：$n \le 3$，$k \le 10^9$ 对于另 $20\%$ 的数据：$n \le 10^6$，$k \le 10^6$ 对于 $80\%$ 的数据（包括上一条）：$n \le 10^6$，$k\le 10^9$ 对于 $100\%$ 的数据：$n\le 10^9$，$0\le k \le 10^{9}$，$0 \le S \le n \times k$。