Melborp Lacissalc

Time limit2sMemory limit1024 MB

Summary

Count length-n arrays over 0 to k-1 for which exactly t consecutive subarrays have a sum divisible by k, modulo 998244353.

Level: Medium6 of 10
Topics: Dynamic programming, Prefix sum, Combinatorics
Solved: No attempts yet

Statement

Grammy has a favorite number $k$ . She thinks that all the numbers divisible by $k$ are good.

For each array containing only numbers from $0$ to $k-1$ , Grammy defines its goodness as the number of non-empty consecutive subarrays that sum to a good number.

Please count the number of arrays of length $n$ such that their goodness is $t$ . Since the answer can be enormous, output the answer modulo $998\,244\,353$ .

Input

A single line contains three integers $n$ , $k$ , $t$ ( $1 \leq n, k \leq 64$ , $0 \leq t \leq \frac{n(n+1)}{2}$ ).

Output

Output a single integer, the answer modulo $998\,244\,353$ .

Examples3

Example 1
Input
```
2 5 1
```
Expected output
```
12
```
Example 2
Input
```
7 10 15
```
Expected output
```
2016
```
Example 3
Input
```
46 50 171
```
Expected output
```
645560469
```