You are given three integers $$$n$$$, $$$k$$$ and $$$f$$$.
Consider all binary strings (i. e. all strings consisting of characters $$$0$$$ and/or $$$1$$$) of length from $$$1$$$ to $$$n$$$. For every such string $$$s$$$, you need to choose an integer $$$c_s$$$ from $$$0$$$ to $$$k$$$.
A multiset of binary strings of length exactly $$$n$$$ is considered beautiful if for every binary string $$$s$$$ with length from $$$1$$$ to $$$n$$$, the number of strings in the multiset such that $$$s$$$ is their prefix is not exceeding $$$c_s$$$.
For example, let $$$n = 2$$$, $$$c_{0} = 3$$$, $$$c_{00} = 1$$$, $$$c_{01} = 2$$$, $$$c_{1} = 1$$$, $$$c_{10} = 2$$$, and $$$c_{11} = 3$$$. The multiset of strings $$$\{11, 01, 00, 01\}$$$ is beautiful, since:
Now, for the problem itself. You have to calculate the number of ways to choose the integer $$$c_s$$$ for every binary string $$$s$$$ of length from $$$1$$$ to $$$n$$$ in such a way that the maximum possible size of a beautiful multiset is exactly $$$f$$$.
The only line of input contains three integers $$$n$$$, $$$k$$$ and $$$f$$$ ($$$1 \le n \le 15$$$; $$$1 \le k, f \le 2 \cdot 10^5$$$).
Print one integer — the number of ways to choose the integer $$$c_s$$$ for every binary string $$$s$$$ of length from $$$1$$$ to $$$n$$$ in such a way that the maximum possible size of a beautiful multiset is exactly $$$f$$$. Since it can be huge, print it modulo $$$998244353$$$.
1 42 2
3
2 37 13
36871576
4 1252 325
861735572
6 153 23699
0
15 200000 198756
612404746
In the first example, the three ways to choose the integers $$$c_s$$$ are:
Name |
---|