题目描述

程老师带学生做手工，材料是一条 $n$ 个格子的彩带。每个格子都要染上颜色，可选的颜色有且只有三种，为了书写方便记作颜色 $0$、颜色 $1$、颜色 $2$；每个格子染且只染一种颜色。

染色有一条禁忌：颜色 $0$ 与颜色 $2$ 不能相邻。只要相邻的两个格子里，一个染的是 $0$、另一个染的是 $2$，不管 $0$ 在前还是 $2$ 在前，这样的染法都不允许。除这一条之外没有别的限制：相邻两格都染 $0$、都染 $1$、都染 $2$ 都可以，$0$ 与 $1$ 相邻、$1$ 与 $2$ 相邻也都可以。

程老师还要数一数一条彩带上有多少同色处：如果第 $i$ 个格子和第 $i + 1$ 个格子染的颜色相同，那么位置 $(i, i+1)$ 就贡献一处同色；整条彩带上这样的位置有几对，就有几处同色。

程老师想知道，在所有不违反禁忌的染法中，恰好有 $k$ 处同色的染法共有多少种。两种染法只要有任意一个格子的颜色不同，就视为不同的染法。答案可能很大，只需要给出它对 $998244353$ 取模的结果。

输入格式

从文件 ribbon.in 中读入数据。

一行两个整数 $n, k$。

输出格式

输出到文件 ribbon.out 中。

一行一个整数，表示满足条件的染法数对 $998244353$ 取模的结果。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 2000$；
• $0 \le k \le n - 1$。

特殊性质 A：$k = 0$。

特殊性质 B：$k \le 2$。

3 1

8

2 0

4

样例解释

样例 1：先不考虑禁忌，三个格子恰好有一处同色，同色的那一对只能出现在 $(1,2)$ 或 $(2,3)$ 这两个位置之一；这对格子的颜色有 $3$ 种选法，剩下的第三个格子只要与这一对颜色不同就行，有 $2$ 种选法，共 $2 \times 3 \times 2 = 12$ 种。把这 $12$ 种逐个看过去，002、200、220、022 这四种在相邻位置上出现了 $0$ 与 $2$，违反禁忌；其余 $8$ 种都不违反，所以答案是 $8$。

样例 2：两个格子没有同色处，说明两格颜色必须不同。从三种颜色里取两种并分先后，得到 01、10、12、21、02、20 六种，其中 02 与 20 两格相邻处恰好是 $0$ 与 $2$，违反禁忌，要排除。剩下 01、10、12、21 共 $4$ 种。