CF1781F.Bracket Insertion

Vika likes playing with bracket sequences. Today she wants to create a new bracket sequence using the following algorithm. Initially, Vika's sequence is an empty string, and then she will repeat the following actions $n$ times:

• Choose a place in the current bracket sequence to insert new brackets uniformly at random. If the length of the current sequence is $k$, then there are $k+1$ such places: before the first bracket, between the first and the second brackets, $\ldots$, after the $k$-th bracket. In particular, there is one such place in an empty bracket sequence.
• Choose string "()" with probability $p$ or string ")(" with probability $1 - p$ and insert it into the chosen place. The length of the bracket sequence will increase by $2$.

A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into it. For example, sequences "(())()", "()", and "(()(()))" are regular, while ")(", "(()", and "(()))(" are not.

Vika wants to know the probability that her bracket sequence will be a regular one at the end. Help her and find this probability modulo $998\,244\,353$ (see Output section).

维卡喜欢玩括号序列。今天，她想用以下算法构造一个新的括号序列：初始时，维卡的序列为空字符串，然后她将重复执行以下操作 $n$ 次：

• 在当前括号序列中均匀随机地选择一个位置插入一对新括号。若当前序列长度为 $k$，则共有 $k+1$ 个可选位置：第一个括号之前、第一个与第二个括号之间、……、第 $k$ 个括号之后。特别地，空括号序列有且仅有一个可选位置。
• 以概率 $p$ 选择字符串 "()"，或以概率 $1 - p$ 选择字符串 ")("，并将该字符串插入所选位置。括号序列的长度因此增加 $2$。

若一个括号序列可通过向其中插入字符 '+' 和 '1' 得到一个合法的算术表达式，则称其为正则括号序列（regular bracket sequence）。例如，"(())()"、"()" 和 "(())" 是正则括号序列，而 ")("、"(()" 和 "(())(" 不是。

维卡想知道：最终得到的括号序列是正则括号序列的概率是多少？请你帮她计算该概率对 $998\,244\,353$ 取模的结果（参见“输出”部分）。

The only line contains two integers $n$ and $q$ ($1 \le n \le 500$; $0 \le q \le 10^4$). Here $n$ is equal to the number of bracket insertion operations, and the probability that Vika chooses string "()" on every step of the algorithm is equal to $p = q \cdot 10^{-4}$.

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

Print the probability that Vika's final bracket sequence will be regular, modulo $998\,244\,353$.

Formally, let $M = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

输出薇卡最终得到的括号序列是合法括号序列的概率，对 $998\,244\,353$ 取模。

形式化地，令 $M = 998\,244\,353$。可以证明该答案可表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first example, Vika will get a regular bracket sequence () with probability $p = \frac{3}{4}$, and she will get an irregular bracket sequence )( with probability $1 - p = \frac{1}{4}$. The sought probability is $\frac{3}{4}$, and $249\,561\,089 \cdot 4 \equiv 3 \pmod{998\,244\,353}$.

In the second example, the sought probability is $\frac{11}{25}$.

在第一个例子中，维卡将以概率 $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}$。