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