Um conjunto de inteiros não negativos é bom se, e somente se, todos os números do conjunto são menores que $T$ e a sua soma é congruente a $rem$ módulo $n$. A sua tarefa é encontrar o número de conjuntos bons distintos.
Entrada
A primeira linha da entrada contém os inteiros $n$ e $rem$, separados por espaços ($0 \le rem < n \le 10^4$). A segunda linha da entrada contém um único inteiro $T$ ($1 \le T \le 10^{100\,000} - 1$).
Saída
Imprima o número de conjuntos bons distintos. Como esse número pode ser muito grande, imprima-o módulo o número primo $998\,244\,353$.
Exemplos
Entrada 1
3 2 5
Saída 1
8
Entrada 2
1 0 20
Saída 2
1048576
Nota
No primeiro exemplo, podemos incluir ou excluir livremente os números $0$ e $3$, pois isso não altera o resto. Entre os números $\{1, 2, 4\}$, há dois conjuntos bons: $\{2\}$ e $\{1, 4\}$. Portanto, a resposta é $2 \cdot 2 \cdot 2 = 8$.
No segundo exemplo, qualquer subconjunto de $\{0, 1, \ldots, 19\}$ é bom, pelo que a resposta é $2^{20} = 1\,048\,576$.