F. Вставка скобок
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вика любит играть со скобочными последовательностями. Сегодня она хочет создать новую скобочную последовательность по следующему алгоритму. Исходно скобочная последовательность Вики — пустая строка, а дальше $$$n$$$ раз она повторит следующие действия:

  • Выберет место в текущей скобочной последовательности, куда можно вставлять скобки, случайно равновероятно среди всех возможных позиций. Если длина текущей последовательности равна $$$k$$$, то таких позиций $$$k+1$$$: перед первой скобкой, между первой и второй скобками, $$$\ldots$$$, после $$$k$$$-й скобки. В частности, в пустой скобочной последовательности одно такое место.
  • Выберет строку «()» с вероятностью $$$p$$$ или строку «)(» с вероятностью $$$1 - p$$$ и вставит её в выбранное место. Длина скобочной последовательности увеличится на $$$2$$$.

Скобочная последовательность называется правильной, если из неё возможно получить корректное арифметическое выражение путём вставки символов «+» и «1». Например, последовательности «(())()», «()» и «(()(()))» являются правильными, а «)(», «(()» и «(()))(» — нет.

Вика хочет знать, с какой вероятностью ее итоговая скобочная последовательность будет правильной. Помогите ей и найдите эту вероятность по модулю $$$998\,244\,353$$$ (см. формат вывода).

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

В единственной строке задано два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 500$$$; $$$0 \le q \le 10^4$$$). Здесь $$$n$$$ равно числу операций вставки скобок, а вероятность выбора Викой строки «()» на каждом шаге алгоритма равна $$$p = q \cdot 10^{-4}$$$.

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

Выведите вероятность того, что скобочная последовательность Вики окажется правильной, по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Примеры
Входные данные
1 7500
Выходные данные
249561089
Входные данные
2 6000
Выходные данные
519087064
Входные данные
5 4000
Выходные данные
119387743
Примечание

В первом примере с вероятностью $$$p = \frac{3}{4}$$$ получится правильная скобочная последовательность (), а с вероятностью $$$1 - p = \frac{1}{4}$$$ получится неправильная скобочная последовательность )(. Искомая вероятность равна $$$\frac{3}{4}$$$, а $$$249\,561\,089 \cdot 4 \equiv 3 \pmod{998\,244\,353}$$$.

Во втором примере искомая вероятность равна $$$\frac{11}{25}$$$.