Melborp Lacissalc

시간 제한2초메모리 제한1024 MB

요약

0부터 k-1까지의 값을 원소로 하는 길이 n 배열 중, 합이 k의 배수가 되는 연속 부분배열의 개수가 정확히 t인 배열의 수를 998244353으로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 조합론, 수학, 동적 계획법, 누적 합
정답자: 아직 제출이 없습니다

문제

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

입력

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 a single integer denoting the answer modulo $998\\,244\\,353$ .

예제3

예제 1
입력
```
2 5 1
```
예상 출력
```
12
```
예제 2
입력
```
7 10 15
```
예상 출력
```
2016
```
예제 3
입력
```
46 50 171
```
예상 출력
```
645560469
```