Множество неотрицательных целых чисел называется хорошим тогда и только тогда, когда все числа в нём меньше $T$, а их сумма сравнима с $rem$ по модулю $n$. Ваша задача — найти количество различных хороших множеств.

Входные данные

Первая строка входных данных содержит целые числа $n$ и $rem$, разделённые пробелом ($0 \le rem < n \le 10^4$). Вторая строка содержит одно целое число $T$ ($1 \le T \le 10^{100\,000}-1$).

Выходные данные

Выведите количество различных хороших множеств. Поскольку оно может быть очень большим, выведите его по модулю простого числа $998\,244\,353$.

Примеры

Входные данные 1

3 2
5

Выходные данные 1

8

Входные данные 2

1 0
20

Выходные данные 2

1048576

Примечание

В первом примере числа $0$ и $3$ можно независимо включать в множество или исключать из него: это не меняет остаток. Из чисел $\{1,2,4\}$ можно составить два хороших множества: $\{2\}$ и $\{1,4\}$. Таким образом, ответ равен $2 \cdot 2 \cdot 2 = 8$.

Во втором примере любое подмножество $\{0,1,\ldots,19\}$ является хорошим, поэтому ответ равен $2^{20}=1\,048\,576$.