题目背景

在化为废墟的城市中，大雨倾盆而降。

「魔女之夜」被击败后，圆和焰也已遍体鳞伤，因魔力不足而倒地不起。

「我们，也已经完了......」圆轻叹道。

「那悲叹之种呢？」焰的语气中还带着一丝希望。

圆沉默不语，望着天空，只是无奈地摇了摇头。

「是吗...... 我说，我们就这样一起变成怪物，把这世界的一切都搞得一团糟吧。」焰说着，不由地啜泣起来。「把那些讨厌的事和悲伤的事，全都和没发生过一样，破坏掉、破坏掉、破坏殆尽...... 你不觉得，这样也很好吗？」

随着一声清脆的碰撞，焰感觉到魔力流入了自己的灵魂宝石内。她转头看见圆正微笑着，拿着一枚悲叹之种。

「刚才那是骗你的，」圆的笑容依旧那么甜美，「我还留着一个呢。」

焰慌忙抱住了圆的手臂，问到：「为什么，为什么要给我？」

「因为有件我做不到，但是小焰能做到的事，我想拜托你...... 小焰，你可以回到过去对吧？你说过，为了避免这样的结局，而改写过历史的吧......」

「嗯...」

圆也终于忍不住悲伤，晶莹的泪珠从她脸上滑落。「你能去救救那个还没被丘比欺骗的，笨蛋的我吗？」

「我答应你，一定会救你的！无论重复多少次，我都会保护好你！」

「太好了......」圆平静了下来，但下一瞬间，她的灵魂宝石中就散出了黑雾，她的表情也痛苦地扭曲了起来。「再......拜托你一件事可以吗？」

焰轻轻点头答应。

「我，不想变成魔女......」圆的声音更加虚弱，「就算有讨厌的事和悲伤的事，但我想守护的东西，在这世上还有很多。」圆艰难地抬起手臂，支撑着手中漆黑的灵魂宝石。

「小圆......」焰拔出手枪，对准了圆的灵魂宝石。在焰的痛哭声中，她扣下了扳机。

题目描述

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

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

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

输入格式

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

输出格式

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

3 0 2

9

3 2 2

198

4 3 2

16008

6 4 2

58351320

514 250 114

354914151

提示

【样例 $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$。