22075번 - Занимательная криптография 다국어

문제

Вася и Петя решили поиграть в шпионов. Вася загадал слово из n строчных английских букв, и сказал Пете, что полиномиальный хеш от этого слова равен x. Ваша задача состоит в том, чтобы помочь Пете узнать, сколько различных слов мог загадать Вася. Так как это число может быть довольно большим, выведите его по модулю 998244353.

Полиномиальный хеш от строки s = a₀a₁…a_{n − 1} — это значение суммы ord(a₀)⋅p⁰ + ord(a₁)⋅p¹ + ... + ord(a_{n − 1})⋅p^{n − 1}, взятое по модулю m, здесь как ord(c) обозначен порядковый номер символа c в латинском алфавите, например ord(a) = 1, ord(b) = 2, ord(z) = 26.

입력

Первая строка содержит четыре целых числа n, m, p и x (1 ≤ n ≤ 10⁶, 2 ≤ m ≤ 10⁴, 1 ≤ p < m, 0 ≤ x < m).

출력

Выведите одно целое число — число слов, которые мог загадать Вася, взятое по модулю 998244353.

제한

힌트