给你三个整数 $$$n$$$、$$$k$$$ 和 $$$f$$$。
考虑长度从 $$$1$$$ 到 $$$n$$$ 的所有二进制字符串(即由字符 $$$0$$$ 和/或 $$$1$$$ 组成的所有字符串)。对于每个这样的字符串 $$$s$$$,您需要选择一个从 $$$0$$$ 到 $$$k$$$ 的整数 $$$c_s$$$。
如果对于长度从 $$$1$$$ 到 $$$n$$$ 的每个二进制字符串 $$$s$$$,多重集中以 $$$s$$$ 为其前缀的字符串数量不超过 $$$c_s$$$,则长度恰好为 $$$n$$$ 的二进制字符串多重集被认为是美丽的。
例如,设 $$$n = 2$$$、$$$c_{0} = 3$$$、$$$c_{00} = 1$$$、$$$c_{01} = 2$$$、$$$c_{1} = 1$$$、$$$c_{10} = 2$$$ 和 $$$c_{11} = 3$$$。字符串多重集 $$$\{11, 01, 00, 01\}$$$ 很漂亮,因为:
- 对于字符串 $$$0$$$,多重集中有 $$$3$$$ 字符串,其中 $$$0$$$ 是它们的前缀,$$$3 \le c_0$$$;
- 对于字符串$$$00$$$,多重集中有一个字符串,$$$00$$$ 是其前缀,$$$1 \le c_{00}$$$;
- 对于字符串 $$$01$$$,多重集中有 $$$2$$$ 字符串,其中 $$$01$$$ 是它们的前缀,$$$2 \le c_{01}$$$;
- 对于字符串 $$$1$$$,多重集中有一个字符串,$$$1$$$ 是其前缀,并且 $$$1 \le c_1$$$;
- 对于字符串 $$$10$$$,多重集中有 $$$0$$$ 字符串,其中 $$$10$$$ 是它们的前缀,$$$0 \le c_{10}$$$;
- 对于字符串 $$$11$$$,多重集中有一个字符串,$$$11$$$ 是其前缀,并且 $$$1 \le c_{11}$$$。
现在,针对问题本身。您必须计算为长度从 $$$1$$$ 到 $$$n$$$ 的每个二进制字符串 $$$s$$$ 选择整数 $$$c_s$$$ 的方法数量,使得美丽多重集的最大可能大小恰好为 $$$f$$$。
输入
输入的唯一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$f$$$ ($$$1 \le n \le 15$$$; $$$1 \le k, f \le 2 \cdot 10^5$$$)。
输出
打印一个整数 — 为每个长度从 $$$1$$$ 到 $$$n$$$ 的二进制字符串 $$$s$$$ 选择整数 $$$c_s$$$ 的方法数,使得美丽多重集的最大可能大小恰好为 $$$f$$$。因为它可能很大,所以打印它对 $$$998244353$$$ 取模。
示例
输入 #1
1 42 2
输出 #1
3
输入 #2
2 37 13
输出 #2
36871576
输入 #3
4 1252 325
输出 #3
861735572
输入#4
6 153 23699
输出#4
0
输入 #5
15 200000 198756
输出 #5
612404746
注意
在第一个示例中,选择整数 $$$c_s$$$ 的三种方法是:
- $$$c_0 = 0$$$, $$$c_1 = 2$$$, 则最大美丽多重集为$$$\{1, 1\}$$$;
- $$$c_0 = 1$$$, $$$c_1 = 1$$$, 则最大美丽多重集为$$$\{0, 1\}$$$;
- $$$c_0 = 2$$$, $$$c_1 = 0$$$,则最大美丽多重集为$$$\{0, 0\}$$$。