您有 $$$n$$$ 筹码,您将把它们全部放在 $$$x$$$ 点之一,编号从 $$$1$$$ 到 $$$x$$$。每个点可以有多个筹码。
放置芯片后,可以执行以下四种操作(任意顺序、任意次数):
- 在点 $$$i \ge 3$$$ 中选择一个筹码,将其移除并放置两个筹码:一个在 $$$i-1$$$ 中,一个在 $$$i-2$$$ 中;
- 选择相邻点$$$i$$$和$$$i+1$$$中的两个筹码,将其移除并在$$$i+2$$$中放置一个新筹码;
- 在$$$1$$$处选择一个筹码并将其移至$$$2$$$;
- 在$$$2$$$点选择一个筹码并将其移动到$$$1$$$。
注意操作时放置的筹码坐标不能小于$$$1$$$,但可以大于$$$x$$$。
将芯片布局成本表示为执行这些操作后线路上可以存在的最小芯片数量(从您选择的布局开始)。
例如,在 $$$3$$$ 点放置 2 个筹码,在 $$$5$$$ 点放置 1 个筹码的成本为 $$$2$$$,因为您可以将筹码数量减少到 $$$2$$$,如下所示:
- 在点$$$3$$$中选择一个筹码,将其移除,在$$$1$$$中放置一个筹码,在$$$2$$$中放置另一个筹码;
- 选择点 $$$2$$$ 和 $$$3$$$ 中的筹码,将其移除并在 $$$4$$$ 中放置筹码;
- 选择点 $$$4$$$ 和 $$$5$$$ 中的筹码,将其移除并在 $$$6$$$ 中放置一个筹码。
给你三个整数 $$$n$$$、$$$x$$$ 和 $$$m$$$。计算从 $$$1$$$ 到 $$$x$$$ 的恰好 $$$n$$$ 筹码的放置数量,成本等于 $$$m$$$,并以 $$$998244353$$$ 为模打印。如果两个布局之间的某些点上的筹码数量不同,则这两个布局被视为不同。
输入
唯一的一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 1000$$$; $$$2 \le x \le 10$$$)。
输出
打印一个整数 — 成本等于 $$$m$$$ 的放置数量,以 $$$998244353$$$ 为模。
示例
输入 #1
2 3 1
输出 #1
5
输入 #2
42 10 5
输出 #2
902673363
输入 #3
1000 10 8
输出 #3
187821763
注意
在第一个示例中,有五种方法可以将 $$$2$$$ 筹码放置在从 $$$1$$$ 到 $$$3$$$ 的点中,以便成本为 $$$1$$$:
- $$$(1, 1)$$$;
- $$$(1, 2)$$$;
- $$$(1, 3)$$$;
- $$$(2, 2)$$$;
- $$$(2, 3)$$$.