Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

brute force

dp

fft

flows

graphs

math

meet-in-the-middle

trees

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Multiset of Strings

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Input

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

Output

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

Examples

Input

1 42 2

Output

3

Input

2 37 13

Output

36871576

Input

4 1252 325

Output

861735572

Input

6 153 23699

Output

0

Input

15 200000 198756

Output

612404746

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/12/2024 20:04:06 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|