18556번 - Count the Sequences 다국어

문제

Given four integers, \(m\), \(b\), \(c\), and \(n\), calculate the number of integer sequences \(x_1, \dots, x_m\) such that:

• \(0 \le x_i \le b^i - c\);
• \(\sum_{i=1}^{m}{x_i} < n\).

Print the answer modulo 998 244 353.

입력

The first line of the input 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}\)).

출력

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

제한

힌트