Expected Longest Valid Parentheses Subsequence

Consider a bracket sequence S of length N. Initially S consists entirely of the character ‘(’. Then a process is performed with a parameter K as follows:

1. Uniformly at random choose an index in [1,N] and flip that bracket (i.e. change '(' to ')' and vice‐versa).
2. If this flip causes the number of '(' in S to decrease then decrease K by 1.
3. Repeat the above until K becomes 0.

At this point, the string S is fixed. We define the longest valid parentheses subsequence of S as follows. (A valid parentheses sequence is one that can be obtained by deleting some characters (possibly none) from S such that the remaining string is a well‐formed parentheses string; note that the subsequence need not be contiguous.) In other words, if you run the following greedy algorithm on S:

balance = 0, pairs = 0
for i = 1 to N:
    if S[i] == '(' then balance++
    else if balance > 0 then { balance--; pairs++; }

then 2×pairs is exactly the length of the longest valid parentheses subsequence. (It is not hard to prove that when deleting characters to form a valid sequence one may pair a right bracket only if there is a left bracket occurring earlier.)

Your task is: Given N and K, compute the expected value of 2 × (number of pairs) (i.e. the expected length of the longest valid parentheses subsequence) after the random process finishes. Since the answer is a rational number, output it modulo $$998244353.$$

Note: In the process the following update is performed repeatedly until K becomes 0:

$$\text{Select } i\in[1,N] \text{ uniformly at random, and set } S_i:=\begin{cases} ) & \text{if } S_i=(,\\ ( & \text{if } S_i=) .\end{cases}$$

If the current move changes a '(' into a ')', then the parameter K is decreased by 1; otherwise it remains unchanged.

inputFormat

The input consists of a single line containing two integers N and K (1 ≤ N ≤ 12, 0 ≤ K ≤ N). Note that N is small so that the random process can be simulated exactly.

For example:

3 1

outputFormat

Output a single integer, the expected length of the longest valid parentheses subsequence (which is 2×(number of matched pairs)) modulo 998244353.

The answer is defined as the sum over all possible outcomes (each with its probability) of the computed length, taken modulo 998244353. It can be shown that the answer is a rational number and under modulo 998244353 it is well–defined.

sample

3 1

332748119