Game

题目描述

游戏是这样的：

• 每次随机一个 $[0, k^n)$ 内的十进制整数，如果将其转换成 $n$ 位 $k$ 进制数后存在连续两位数相同，那么就会得到 $x$ 的分值。

问游戏的期望得分是多少，答案对 $998244353$ 取模。

输入格式

输入 $n,k,x$。

输出格式

输出期望得分。

样例 #1

样例输入 #1

3 2 2

样例输出 #1

499122178

提示

一共有 $8$ 个数在 $[0, 2^3)$ 的范围中，其中 $6$ 个数可以各获得 $2$ 分，答案为 $\dfrac18 \times 6 \times 2 = \dfrac 32$，由于 $\dfrac 23 \equiv 499122178 \pmod {998244353}$，故答案为 $499122178$。

对于所有数据，$2 \le n, k, x \le 10^9$