Description

澪正陪着铃一起 N 刷《魔法少女小圆》，看到全剧最催人泪下的情节之一时，家长却突然推门进来了。澪不想被发现自己在摸鱼，就迅速切换界面，假装她们在做一道计数题：

定义一棵有标号、有根、不区分左右儿子的二叉树的权值是：以「根节点的所有儿子节点」为根的子树的权值之和加上 $d$，特别定义只有一个节点的树权值为 $1$。求所有 $n$ 个节点的这种树权值的 $k$ 次方和，答案对 $998244353$ 取模。

「这不是那个什么 NaCly_Fish's Math Contest 的题... 吗？」铃看了看题，小声说道，「好无聊哦，不看这题。」

Input Format

输入一行三个正整数 $n,k,d$。

Output Format

输出一行一个整数，表示答案。

3 0 2

9

3 2 2

198

4 3 2

16008

6 4 2

58351320

514 250 114

354914151

Hint

【样例 $1$ 解释】

$3$ 个节点的有标号有根二叉树有 $9$ 种，分别如下，其中标红的节点表示树根。
由于 $k=0$，所有树权值的 $k$ 次方和就等于树的总数，故答案为 $9$。

【样例 $2$ 解释】
接上图，图中第一行的树权值都为 $5$，第二行的树权值为 $4$，故答案为 $6\times 5^2+3\times 4^2=198$。

【数据范围】

本题采用捆绑测试。

Subtask1（5 pts）：$n \le 6$；
Subtask2（9 pts）：$k=0$，$n\le 10^7$；
Subtask3（14 pts）：$n\le 10^5$；
Subtask4（18 pts）：$k \le 4000$，$n\le 10^7$；
Subtask5（23 pts）：$k \le 10^5$；
Subtask6（31 pts）：无特殊限制。

对于 $100\%$ 的数据，$2\le n,d \le 9\times 10^8$，$0\le k \le 5\times 10^6$。