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

给你三个整数 $n$、$k$ 和 $f$。

考虑所有长度为 $1$ 到 $n$ 的二进制字符串（即仅由字符 $0$ 和/或 $1$ 构成的字符串）。对每个这样的字符串 $s$，你需要选择一个整数 $c_s$，其取值范围为 $0$ 到 $k$（含端点）。

一个长度恰好为 $n$ 的二进制字符串多重集被称为优美的（beautiful），当且仅当：对每个长度为 $1$ 到 $n$ 的二进制字符串 $s$，该多重集中以 $s$ 为前缀的字符串个数不超过 $c_s$。

例如，设 $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$ 个字符串以其为前缀，且 $3 \le c_0$；
• 对于字符串 $00$，多重集中有 $1$ 个字符串以其为前缀，且 $1 \le c_{00}$；
• 对于字符串 $01$，多重集中有 $2$ 个字符串以其为前缀，且 $2 \le c_{01}$；
• 对于字符串 $1$，多重集中有 $1$ 个字符串以其为前缀，且 $1 \le c_1$；
• 对于字符串 $10$，多重集中有 $0$ 个字符串以其为前缀，且 $0 \le c_{10}$；
• 对于字符串 $11$，多重集中有 $1$ 个字符串以其为前缀，且 $1 \le c_{11}$。

现在，回到本题本身：你需要计算有多少种方式为每个长度为 $1$ 到 $n$ 的二进制字符串 $s$ 选择整数 $c_s$，使得优美多重集的最大可能大小恰好等于 $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$).

输入仅有一行，包含三个整数 $n$、$k$ 和 $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$ 到 $n$ 的二进制字符串 $s$ 选择整数 $c_s$ 的方案数，使得优美多重集的最大可能大小恰好为 $f$。由于答案可能非常大，请对 $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}$.

在第一个例子中，选择整数 $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}$。