时空限制

1S/512M

题目描述

班上有 $n$ 个小组，小组的编号为 $1\sim n$。每个小组有 $k$ 名同学，$k$ 为奇数，共有 $n\times k$ 名同学，同学的编号为 $1\sim n\times k$。

现在需要通过投票确定班服的款式，有款式 $1$ 和款式 $2$ 两个选项。投票的规则为：每个同学投出一票支持款式 $1$ 或者款式 $2$，然后每个小组统计组内同学的投票情况，如果本小组中支持款式 $1$ 的票更多那么视为整个小组支持款式 $1$，否则视为整个小组支持款式 $2$。

已知编号 $1\sim a$ 的同学支持款式 $1$，编号 $a+1\sim n\times k$ 的同学支持款式 $2$。求有多少种不同的分组方案使得最终的投票结果为恰好有 $x$ 个小组支持款式 $1$，对 $998244353$ 取模。如果任意一名同学在两个分组方案中被分到了不同的组，这两个分组方案视为不同方案。

格式

输入格式

第一行包含四个整数 $n,k,a,x$，分别表示小组的数量、每个小组的人数、支持款式 $1$ 的人数以及最终投票结果为恰好有 $x$ 个小组支持款式 $1$。

输出格式

输出一个整数表示满足条件的不同分组方案的数量。对 $998244353$ 取模。

样例

样例输入 #1

3 3 5 1

样例输出 #1

360

样例输入 #2

3 3 5 3

样例输出 #2

0

样例输入 #3

8 9 37 1

样例输出 #3

787613484

样例输入 #4

8 9 37 7

样例输出 #4

483033194

数据规模

对于 $30\%$ 的数据，$n\leq 10$，$k=3$。

另有 $30\%$ 的数据，$n\leq 3$。

对于 $100\%$ 的数据，$1\leq n\leq 100$，$3\leq k\leq 9$，$0\leq a\leq n\times k$，$0\leq x\leq n$。数据保证 $k$ 为奇数。