P6689 序列

小 C 想出关于括号序列的一道题，但是他不怎么会造数据，所以他采取了随机的方式。 小 C 钦定了括号序列 $S$ 的长度 $N$。$S$ 初始时全为 `(`。 他初始设定了一个参数 $K$，并按照如下流程随机，直到 $K=0$： 1. 在 $[1,N]$ 的范围内**均匀随机**一个整数，把 $S$ 这一位上的括号取反（左括号变右括号，右括号变左括号）。 2. 如果本次操作使得 `(` 的数量减少了，使 $K$ 的值减 $1$。 现在数据造好了，题也就出完了。 小 C 想请你求出，在经过上述操作后，$S$ 中**最长合法括号子序列**（不要求连续）在模 $998244353$ 意义下期望有多长。

无

无

**样例解释1** 最终括号序列只有 $3$ 种，`))`，`()`，`)(`。其对应的概率分别为 $\frac{1}{2}$，$\frac{1}{4}$，$\frac{1}{4}$。 它们对应的最长合法括号子序列长度分别为 $0,2,0$。所以最终答案为 $\frac{1}{2}$，也即 $499122177$。 **数据规模：** 对于前 $5\%$ 的数据，$N=1$； 另有 $5\%$ 的数据，$N=2$； 另有 $5\%$ 的数据，$N\le 7$，$K\le 5$； 另有 $15\%$ 的数据，$N\le 15$，$K\le 500$； 另有 $ 15\%$ 的数据，$N\le 50$，$K\le 50$； 另有 $ 15\%$ 的数据，$N\le 500$，$K\le 100$； 对于全部的数据，保证 $1\le N,K\le 5000$。