括号插入

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

Vika 从空字符串开始，执行恰好 $n$ 次操作。若当前字符串长度为 $k$，她会从 $k+1$ 个插入位置中等概率选择一个位置；随后以概率 $p$ 插入字符串 “()”，以概率 $1-p$ 插入字符串 “)(”。每次操作后字符串长度增加 $2$。

一个括号序列称为合法括号序列，当且仅当把左括号视为 $1$、右括号视为 $-1$ 后，所有前缀和均非负，且整个序列的和为 $0$。

已知每一步插入 “()” 的概率为 $p=q\cdot 10^{-4}$。求执行 $n$ 次操作后得到合法括号序列的概率，并对 $998\,244\,353$ 取模。

输入格式

一行包含两个整数 $n,q$，分别表示操作次数与概率参数。

输出格式

输出所求概率对 $998\,244\,353$ 取模后的值。

形式化地，设答案是最简分数 $\frac{a}{b}$，且 $b\not\equiv0\pmod{998\,244\,353}$。输出唯一的整数 $x$，满足 $0\le x<998\,244\,353$ 且 $xb\equiv a\pmod{998\,244\,353}$。

样例输入 1

1 7500

样例输出 1

249561089

样例输入 2

2 6000

样例输出 2

519087064

样例输入 3

5 4000

样例输出 3

119387743

数据范围

$1\le n\le500$，$0\le q\le10^4$。