CF1709F Multiset of Strings

给定三个整数 $n$、$k$ 和 $f$。 考虑所有长度从 $1$ 到 $n$ 的二进制字符串（即所有仅由字符 $0$ 和/或 $1$ 组成的字符串）。对于每个这样的字符串 $s$，你需要为其选择一个整数 $c_s$，满足 $0 \le c_s \le k$。 如果一个长度恰好为 $n$ 的二进制字符串多重集满足：对于每个长度从 $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$，多重集中以 $0$ 为前缀的字符串有 $3$ 个，且 $3 \le c_0$； - 对于字符串 $00$，多重集中以 $00$ 为前缀的字符串有 $1$ 个，且 $1 \le c_{00}$； - 对于字符串 $01$，多重集中以 $01$ 为前缀的字符串有 $2$ 个，且 $2 \le c_{01}$； - 对于字符串 $1$，多重集中以 $1$ 为前缀的字符串有 $1$ 个，且 $1 \le c_1$； - 对于字符串 $10$，多重集中以 $10$ 为前缀的字符串有 $0$ 个，且 $0 \le c_{10}$； - 对于字符串 $11$，多重集中以 $11$ 为前缀的字符串有 $1$ 个，且 $1 \le c_{11}$。 现在，问题来了。你需要计算有多少种方式为每个长度从 $1$ 到 $n$ 的二进制字符串 $s$ 选择整数 $c_s$，使得美丽多重集的最大可能大小恰好为 $f$。

输入仅一行，包含三个整数 $n$、$k$ 和 $f$，满足 $1 \le n \le 15$，$1 \le k, f \le 2 \times 10^5$。

输出一个整数，表示有多少种方式为每个长度从 $1$ 到 $n$ 的二进制字符串 $s$ 选择整数 $c_s$，使得美丽多重集的最大可能大小恰好为 $f$。由于答案可能很大，请输出对 $998244353$ 取模后的结果。

在第一个样例中，有三种方式选择整数 $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\}$。 由 ChatGPT 4.1 翻译