如果一个非负整数集合中的所有元素都小于 $T$，且它们的和模 $n$ 的余数为 $rem$，则称该集合为“好的”。你的任务是求出不同的“好的”集合的数量。

输入格式

第一行包含两个空格分隔的整数 $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, \dots, 19\}$ 的任何子集都是“好的”，因此答案为 $2^{20} = 1\,048\,576$。