Count the Sequences

Time limit1sMemory limit512 MB

Summary

Count sequences x_1 to x_m where each 0 <= x_i <= b^i - c and the sum is below n, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Four integers $m$ , $b$ , $c$ , and $n$ are given. Count the integer sequences $x_1, \dots, x_m$ that satisfy the following conditions:

$0 \le x_i \le b^i - c$
$\sum_{i=1}^{m} x_i < n$

Print the answer modulo 998 244 353.

Input

The first line contains three integers $m$ , $b$ , and $c$ ( $1 \le m \le 50$ , $2 \le b \le 10^9$ , $-b+2 \le c \le b-1$ ). The second line contains a large integer $n$ ( $1 \le n \le b^{n+1}$ ).

Output

Print one integer, the number of sequences modulo 998 244 353.

Examples1

Example 1
Input
```
2 3 1
5
```
Expected output
```
12
```