Given $m, b, c, n$, please calculate the number of sequence $x_1, x_2, x_3, \dots, x_m$ which satisfies : $0 \leq x_i\leq b ^ i - c, x_i \in \mathbb{Z}$ $\sum_{i = 1}^{m}{x_i} < n$. Output the answer module 998244353. $1\leq m\leq 50$ $2\leq b \leq 10^9, -b + 2 \leq c \leq b - 1$ $1\leq n< b^{m + 1}$
输入解释
There are several test cases, please keep reading until EOF. For each test case, the first line consists of 3 integers $m, b, c$. The next line consists of a big integer $n$. There are 10 test cases.
输出解释
For each test case, output Case #x: y, which means the the test case number and the answer.