Count the Sequences

0 ≤ x_i ≤ b^i - c이고 합이 n보다 작은 정수 수열 x_1, ..., x_m의 개수를 998244353으로 나눈 나머지로 구한다.

어려움9조합론동적 계획법수학정수론아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제 설명

예제1

문제

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.