题目描述

对于一个长度为 $n$ 的 $\text{0-1}$ 序列 $s$，我们将它的位从左到右、从零开始编号，记为 $s_0, s_1, \ldots , s_{n-1}$。

给定一个正整数 $k$，从 $s$ 中取出某个长度为 $k$ 的子段。将这个子段解释为一个左侧为高位、右侧为低位的 $k$ 位二进制数，记为 $t$，则有 $0 \le t < 2^k$。

$s$ 有 $n - k + 1$ 个长度为 $k$ 的子段，如果对于其中的每一个子段，如上解释为二进制数 $t$ 后，$s$ 的编号为 $t$ 的位（即 $s_t$）都是 $1$，则说 $s$ 是合法的。保证 $2^k \le n$，即 $t$ 作为 $s$ 的下标不会越界。

给定 $n, k$，求合法的 $s$ 的数量。由于方案数可能较大，只需给出方案数模 $998,244,353$ 的结果作为答案。

输入格式

输入有一行，包含两个用空格隔开的正整数 $n, k$。

保证 $1 \le k \le 4$，$2^k \le n \le 500$。

输出格式

输出一行，包含一个非负整数，即合法方案数模 $998,244,353$ 的结果。

样例

4 2

2

有两个满足要求的序列：$0, 1, 1, 1$ 和 $1, 1, 1, 1$。

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。