A15178. Multiset of Strings

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:

- for the string $0$ , there are $3$ strings in the multiset such that $0$ is their prefix, and $3 \le c_0$ ;
- for the string $00$ , there is one string in the multiset such that $00$ is its prefix, and $1 \le c_{00}$ ;
- for the string $01$ , there are $2$ strings in the multiset such that $01$ is their prefix, and $2 \le c_{01}$ ;
- for the string $1$ , there is one string in the multiset such that $1$ is its prefix, and $1 \le c_1$ ;
- for the string $10$ , there are $0$ strings in the multiset such that $10$ is their prefix, and $0 \le c_{10}$ ;
- for the string $11$ , there is one string in the multiset such that $11$ is its prefix, and $1 \le c_{11}$ .

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$ .

In the first example, the three ways to choose the integers $c_s$ are:

- $c_0 = 0$ , $c_1 = 2$ , then the maximum beautiful multiset is $\{1, 1\}$ ;
- $c_0 = 1$ , $c_1 = 1$ , then the maximum beautiful multiset is $\{0, 1\}$ ;
- $c_0 = 2$ , $c_1 = 0$ , then the maximum beautiful multiset is $\{0, 0\}$ .