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

Нарешті настали літні канікули, і 久莲 вирішила запросити друзів поплавати. Спершу вона хоче відгородити прямокутну ділянку моря біля приватного пляжу своєї родини, щоб облаштувати місце для плавання. Проте море приховує різні небезпеки: десь надто глибоко, а десь водяться отруйні медузи. Вона хоче, щоб уся відгороджена ділянка була безпечною.

Після попереднього аналізу вона подала цю ділянку моря як прямокутну сітку з основою завдовжки $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<998\,244\,353$. Значення $q$ дорівнює $\frac{x}{y}$.

Вихідні дані

Виведіть дані у файл pool.out.

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

Тобто нехай відповідь у вигляді нескоротного дробу дорівнює $\frac ab$, де $a$ та $b$ взаємно прості. Виведіть ціле число $x$, для якого $bx\equiv a\pmod{998\,244\,353}$ та $0\le x<998\,244\,353$. Можна довести, що таке ціле число $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)$.

Підзадачі