가장 큰 집합

음이 아닌 정수들의 집합이 적합하다는 것은, 집합의 모든 수가 $T$보다 작고 그 합을 $n$으로 나눈 나머지가 $\mathit{rem}$과 같다는 뜻이다. 서로 다른 적합한 집합의 개수를 구하라.

첫 줄에 공백으로 구분된 정수 $n$과 $\mathit{rem}$이 주어진다 ($0 \le \mathit{rem} < n \le 10^4$). 둘째 줄에는 정수 $T$가 하나 주어진다 ($1 \le T \le 10^{100\,000} - 1$).

서로 다른 적합한 집합의 개수를 소수 $998\,244\,353$으로 나눈 나머지를 출력한다. 이 개수는 매우 커질 수 있다.

첫 번째 예제에서 $0$과 $3$은 나머지를 바꾸지 않으므로 포함하거나 제외하는 것을 자유롭게 정할 수 있다. 수 $\{ 1, 2, 4 \}$에서는 적합한 집합이 $\{ 2 \}$와 $\{ 1, 4 \}$ 두 개뿐이다. 따라서 답은 $2 \times 2 \times 2 = 8$이다.

두 번째 예제에서는 $\{ 0, 1, \ldots, 19 \}$의 모든 부분집합이 적합하다. 따라서 답은 $2^{20} = 1\,048\,576$이다.