Vika 喜欢玩括号序列。今天,她想使用以下算法创建一个新的括号序列。最初,Vika 的序列是一个空字符串,然后她将重复以下操作 $$$n$$$ 次:
- 在当前括号序列中选择一个位置,统一随机插入新括号。如果当前序列的长度是$$$k$$$,则有$$$k+1$$$这样的地方:第一个括号之前,第一个和第二个括号之间,$$$\ldots$$$,第$$$k$$$之后。特别是,在空括号序列中有一个这样的位置。
- 以 $$$p$$$ 的概率选择字符串 "()" 或以 $$$1 - p$$$ 的概率选择字符串 ")(" 并将其插入到所选位置。括号序列的长度将增加 $$$2$$$。
如果可以通过在括号序列中插入字符“+”和“1”来获得正确的算术表达式,则该括号序列称为正则括号序列。例如,序列“(())()”、“()”和“(()(()))”是规则的,而“)(”、“(()”和“(()))(”则不是。
Vika 想知道她的括号序列最后是常规序列的概率。帮助她找到这个概率模$$$998\,244\,353$$$(参见输出部分)。
输入
唯一的一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 500$$$; $$$0 \le q \le 10^4$$$)。这里$$$n$$$等于括号插入操作的次数,而Vika在算法的每一步选择字符串“()”的概率等于$$$p = q \cdot 10^{-4}$$$。
输出
打印 Vika 最终括号序列为正则的概率,以 $$$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
1 7500
输出 #1
249561089
输入 #2
2 6000
输出 #2
519087064
输入 #3
5 4000
输出 #3
119387743
注意
在第一个例子中,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}$$$。