시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

2 3 1
5

예제 출력 1

12