#WoC2410. 重构蝶影的海渊

重构蝶影的海渊

重构蝶影的深渊

题目背景

追寻着你的身影,从迷失的世界起航,直到深海的尽头……

题目描述

我们假设量子之海是一条数轴 ,在数轴的1n1 \sim n范围上分布着 kk 个双向传送门,也就是有 2k2k 个门。

每个位置只能摆放一个门,每个传送门只能被激活一次,但不能被连续激活,比如有个传送门 (13)(1,3) ,你不能从1传送到3后马上又传送回1。换句话说,传送后强制前进一格

传送门之间互不影响

如果通过了所有的 2k2k 个传送门,那么称之为重构。

现在布洛妮娅在数轴的 00 处,朝正方向移动。请问有多少种摆设传送门的方法可以使得布洛妮娅达成“重构”,成为理之律者。

kk 个传送门视为相同。例如 12341\to2,3\to434123\to4,1\to2为同一种方案。

输入格式

一行,两个正整数n,kn,k

输出格式

一个正整数,表示答案,对 998244353998244353 取模。

样例

输入#1

5 2

输出#2

5

说明

样例解释:

其中一种连接方式为 14,251↔4,2↔5,布洛妮娅的行走路线为014523412560→1→4→5→2→3→4→1→2→5→6,一共被传送44次。

数据规模与约定

1n105,0kmin(n,8)1\le n\le 10^5, 0 \le k \le min(n, 8)