久莲 — девочка, которая любит развлечения.

Наконец наступили летние каникулы. 久莲 решила пригласить друзей поплавать. Она собирается огородить прямоугольный участок моря у принадлежащего её семье частного пляжа и устроить там место для плавания. Но в море встречаются разные опасности: где-то слишком глубоко, а где-то водятся ядовитые медузы. Она хочет, чтобы весь огороженный участок был безопасным.

После предварительного анализа она представила этот участок моря прямоугольной сеткой с основанием длины $N$ метров и высотой $1001$ метр. Нижняя сторона сетки соответствует её частному пляжу. Каждый квадрат $1\times1$ обозначает единичный участок моря. Она попросила папу завтра измерить, безопасен ли каждый квадрат. Получив эти сведения, она сможет огородить место для плавания.

Её идеальное место для плавания удовлетворяет трём условиям:

• Оно должно быть безопасным: каждый входящий в него единичный участок моря безопасен.
• Оно должно быть прямоугольным: это подсетка размера $a\times b$ всей сетки.
• Оно должно примыкать к пляжу: его нижняя граница должна совпадать с нижней границей сетки.

Например, при $N=5$ результаты измерений могут выглядеть так (поскольку $1001$ — слишком большое число, показаны только три нижние строки сетки; все остальные участки опасны).

Тогда можно выбрать участок $1\times4$ в самой нижней строке или участок $3\times1$ в третьем столбце. Обратите внимание: выбрать участок $1\times5$ в верхней показанной строке нельзя, поскольку он не примыкает к пляжу.

Чтобы друзьям было веселее, она хочет сделать площадь места для плавания как можно больше. Поэтому окончательным выбором станет участок $1\times4$ в самой нижней строке.

Хотя безопасность каждого единичного участка станет известна только завтра, ей уже сейчас хочется оценить площадь своего места для плавания. После несложных прикидок она предположила, что каждый единичный участок независимо безопасен с вероятностью $q$ и опасен с вероятностью $1-q$. Она хочет узнать вероятность того, что максимальная площадь места для плавания, которое она сможет выбрать, будет в точности равна $K$.

Однако 久莲 не интересуется математикой, поэтому просит вас помочь вычислить это значение.

Входные данные

Данные считываются из файла pool.in.

Одна строка содержит четыре положительных целых числа $N,K,x,y$, где $1\le x<y<998244353$. Значение $q$ равно $\frac{x}{y}$.

Выходные данные

Результат выводится в файл pool.out.

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

Иными словами, пусть ответ в виде несократимой дроби равен $\frac{a}{b}$, где $a$ и $b$ взаимно просты. Выведите целое число $x$, для которого $bx\equiv a\pmod{998244353}$ и $0\le x<998244353$. Можно доказать, что такое целое число $x$ единственно.

Примеры

Входные данные 1

10 5 1 2

Выходные данные 1

342025319

Пример 2

См. файлы pool/pool2.in и pool/pool2.ans в каталоге участника.

Пример 3

См. файлы pool/pool3.in и pool/pool3.ans в каталоге участника.

Примечание

$x^{p-1}\equiv1\pmod p$, где $p$ — простое число, $x\in[1,p)$.

Подзадачи