시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB131133.333%

문제

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

Полиномиальный хеш от строки s = a0a1…an − 1 — это значение суммы ord(a0)⋅p0 + ord(a1)⋅p1 + ... + ord(an − 1)⋅pn − 1, взятое по модулю m, здесь как ord(c) обозначен порядковый номер символа c в латинском алфавите, например ord(a) = 1, ord(b) = 2, ord(z) = 26.

입력

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

출력

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

예제 입력 1

1 10 8 7

예제 출력 1

2