「KDOI-02」一个仇的复
题目背景
**本题由于 OI 赛制,关闭 subtask,可能会放部分错解高分,赛后将开启 subtask。**
「听说那件事了吗?愿他们安息。」
「诶?你看,前面那座环形建筑是什么?」
「等我对比一下……啊哈!这就是他们的老巢!」
「捣毁了它,为牺牲的同志们报仇!!!」
死亡的宇宙射线指向了脆弱的文明,正准备发出它震耳欲聋的怒吼。
题目描述
外星人的空间站是一个环形结构。不过,由于环的两段不连通,因此可以将其近似为 $2\times n$ 的平面网格。目前,地方飞船有 $n$ 种不同规格的射线武器,作用范围是 $1\times x$($x$ 为正整数)的长方形。并且,武器可以往顺时针或逆时针方向旋转 $90^\circ$。射线十分强力,只需一发便可与作用范围平面内的所有物体相湮灭。不过,只要宇宙射线的一部分作用范围落到目标外,便会一直延续到宇宙尽头,贪婪地吞噬沿途的一切。指挥官当然不想危害到无辜文明,他想知道,在这 $n$ 中武器中选出 $k$ 种,共有多少种不同的摧毁飞行器的方式。
**【形式化题意】**
你有 $1\times x$($x$ 为任意正整数)的矩形各无穷多个和一个 $2\times n$ 的网格,请求出恰好选择其中 $k$ 个矩形(可以选择相同的矩形)**不重不漏**地铺满整个网格的方案数。矩形可以旋转。
输入输出格式
输入格式
从标准输入中读入数据。
输入共包含一行两个正整数 $n,k$。
输出格式
输出到标准输出。
输出一行一个正整数,表示方案数,答案对 $998244353$ 取模。
输入输出样例
输入样例 #1
4 3
输出样例 #1
8
输入样例 #2
15 5
输出样例 #2
4015
输入样例 #3
3050 1314
输出样例 #3
670638639
输入样例 #4
19198114 4154
输出样例 #4
264122135
说明
****
**【样例解释】**
+ **样例 1 解释:**
共有如下图所示的 $8$ 种方案。
![](https://cdn.luogu.com.cn/upload/image_hosting/iko97ksh.png)
***
**【数据范围】**
对于 $100\%$ 的数据,$1\le n\le 2\times 10^7$,$1\le k\le 5000$。
| 测试点编号 | 分值 | $n$ | $k$ |
| :----------: | :----------: | :----------: | :----------: |
|$1\sim 5$| $2$ | $\leq5$ | $\leq10$ |
|$6\sim 10$| $2$ | $\leq1000$ | $=2n$ |
|$11\sim 15$| $2$ | $\leq10^6$ | $\leq3$ |
|$16\sim 20$| $4$ | $\leq1000$ | $\leq2n$ |
|$21\sim 25$| $4$ | $\leq2\times10^7$ | $\leq100$ |
|$26\sim 30$| $4$ | $\leq10^6$ | $\leq5000$ |
|$31\sim 40$| $1$ | $\leq2\times10^7$ | $\leq5000$ |
注意:分值一列指的是单个测试点分值。