Серед послідовностей довжини \(K\), що складаються з цілих чисел, \(A=(A_1, \ldots, A_K)\), скільки відповідає всім наведеним нижче умовам? Знайдіть число за модулем 998244353.

• \(0 \leq A_i \leq M-1\) для кожного \(i\) (\(1 \leq i \leq K\)).

• \(\displaystyle\prod_{i=1}^{K} A_i \equiv N \pmod M\).

Обмеження

• \(1 \leq K \leq 10^9\)

• \(0 \leq N \lt M \leq 10^{12}\)

Формат вхідних даних

Вхідний потік містить цілі числа \(K, N, M\)

Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану кількість

Примітка

До прикладу 1:

П’ять послідовностей A, що задовольняють умовам, є (1,3),(3,1),(3,3),(3,5),(5,3)

Приклад вхідних даних

2 3 6

Приклад вихідних даних

5

Приклад вхідних даних

10 0 2

Приклад вихідних даних

1023

Приклад вхідних даних

1000000000 20220326 1000000000000

Приклад вихідних даних

561382653