問題文
K 個の整数からなる多重集合 A があります。A の各要素は 1 以上 2N 未満の整数です。
A を使って Alice と Bob がゲームをします。Alice から始めて 2 人は交互に以下の操作を繰り返します。
- 1 以上の整数が書かれた要素を 1 つ選ぶ。選んだ要素の値が X のとき、その要素を 0 以上 X 未満の整数に置き換える。
先に操作ができなくなったプレイヤーが負けで、負けなかったプレイヤーが勝ちです。
A として考えられる全ての多重集合のうち、Bob がどのような操作をしても Alice が必ず勝てる多重集合の種類数を 998244353 で割った余りで求めて下さい。
制約
- 1≤N≤20
- 1≤K≤220
- 入力はすべて整数
入力
出力
1 行に答えを出力してください。
サンプル
A として {1,1},{1,2},{1,3},{2,2},{2,3},{3,3} の 6 種類が考えられます。
このうち Alice が必ず勝てるものは {1,2},{1,3},{2,3} の 3 種類です。
998244353 で割った余りで出力することに注意してください。