Вика любит играть со скобочными последовательностями. Сегодня она хочет создать новую скобочную последовательность по следующему алгоритму. Исходно скобочная последовательность Вики — пустая строка, а дальше \(n\) раз она повторит следующие действия:
- Выберет место в текущей скобочной последовательности, куда можно вставлять скобки, случайно равновероятно среди всех возможных позиций. Если длина текущей последовательности равна \(k\), то таких позиций \(k+1\): перед первой скобкой, между первой и второй скобками, \(\ldots\), после \(k\)-й скобки. В частности, в пустой скобочной последовательности одно такое место.
- Выберет строку «()» с вероятностью \(p\) или строку «)(» с вероятностью \(1 - p\) и вставит её в выбранное место. Длина скобочной последовательности увеличится на \(2\).
Скобочная последовательность называется правильной, если из неё возможно получить корректное арифметическое выражение путём вставки символов «+» и «1». Например, последовательности «(())()», «()» и «(()(()))» являются правильными, а «)(», «(()» и «(()))(» — нет.
Вика хочет знать, с какой вероятностью ее итоговая скобочная последовательность будет правильной. Помогите ей и найдите эту вероятность по модулю \(998\,244\,353\) (см. формат вывода).
Выходные данные
Выведите вероятность того, что скобочная последовательность Вики окажется правильной, по модулю \(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}\).
Примечание
В первом примере с вероятностью \(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}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 7500
|
249561089
|
|
2
|
2 6000
|
519087064
|
|
3
|
5 4000
|
119387743
|