时空限制

1S/512M

题目描述

定义一个数的重复度为出现最多的数位的出现次数，比如 $443$ 的重复度为 $2$，因为 $4$ 出现了 $2$ 次。

求 $n$ 位 $m$ 进制数（可以有“前导 0”，比如 '$\text{01020}$' 是一个 $5$ 位数字）中，重复度不超过 $k$ 的数字个数，对 $998244353$ 取模。

格式

输入格式

第一行包含三个正整数 $n$, $m$, $k$，分别表示数字的长度、进制以及重复度的限制。

输出格式

输出一个整数，表示满足条件的数字个数，对 $998244353$ 取模。

样例

样例输入 #1

3 10 2

样例输出 #1

990

数据规模

对于 $100\%$ 的数据，$1\leq k \leq n\leq 100$， $1\leq m\leq 100$。