Một tập hợp các số nguyên không âm được gọi là tốt khi và chỉ khi mọi số trong tập đều nhỏ hơn $T$ và tổng của chúng đồng dư với $rem$ theo modulo $n$. Nhiệm vụ của bạn là tìm số tập hợp tốt khác nhau.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa các số nguyên $n$ và $rem$ cách nhau bởi dấu cách ($0 \le rem < n \le 10^4$). Dòng thứ hai của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^{100\,000} - 1$).

Dữ liệu ra

In ra số tập hợp tốt khác nhau. Vì số này có thể rất lớn, hãy in phần dư của nó khi chia cho số nguyên tố $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

3 2
5

Dữ liệu ra 1

8

Dữ liệu vào 2

1 0
20

Dữ liệu ra 2

1048576

Ghi chú

Trong ví dụ thứ nhất, ta có thể tùy ý chọn hoặc không chọn các số $0$ và $3$ mà không làm thay đổi số dư. Từ các số $\{1, 2, 4\}$, có hai tập hợp tốt: $\{2\}$ và $\{1, 4\}$. Vì vậy, đáp án là $2 \cdot 2 \cdot 2 = 8$.

Trong ví dụ thứ hai, bất kỳ tập con nào của $\{0, 1, \ldots, 19\}$ đều tốt, do đó đáp án là $2^{20} = 1\,048\,576$.