CF1781F Bracket Insertion

Vika 喜欢玩括号序列。今天她想用如下算法生成一个新的括号序列。起初，Vika 的序列是一个空字符串，然后她会重复以下操作 $n$ 次： - 在当前括号序列中的某个位置等概率地插入新的括号。如果当前序列长度为 $k$，那么有 $k+1$ 个插入位置：第一个括号之前、第一个和第二个括号之间、$\ldots$、第 $k$ 个括号之后。特别地，对于一个空的括号序列，有一个插入位置。 - 以概率 $p$ 选择字符串 "()"，或者以概率 $1-p$ 选择字符串 ")("，并将其插入到选定的位置。括号序列的长度会增加 $2$。 如果一个括号序列可以通过在其中插入字符 '+' 和 '1' 得到一个正确的算术表达式，则称其为合法括号序列。例如，"(())()"、"()" 和 "(()(()))" 是合法的，而 ")("、"(()" 和 "(()))(" 不是合法的。 Vika 想知道她最终得到的括号序列是合法括号序列的概率。请你帮她计算这个概率，并对 $998\,244\,353$ 取模后输出（见输出格式部分）。

一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 500$；$0 \leq q \leq 10^4$）。其中 $n$ 表示括号插入操作的次数，每一步选择字符串 "()" 的概率为 $p = q \cdot 10^{-4}$。

输出 Vika 最终得到的括号序列为合法括号序列的概率，对 $998\,244\,353$ 取模。 形式化地，设 $M = 998\,244\,353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。请输出一个整数 $x$，满足 $0 \leq x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个样例中，Vika 以概率 $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}$。 由 ChatGPT 4.1 翻译