simple counting problem

Problem Description

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}$

Input

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.

Output

For each test case, output Case #x: y, which means the the test case number and the answer.

Sample Input

2 2 1

3

Sample Output

Case #1: 5

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6056