约定（Promise）
题目背景
在化为废墟的城市中，大雨倾盆而降。
「魔女之夜」被击败后，圆和焰也已遍体鳞伤，因魔力不足而倒地不起。
「我们，也已经完了......」圆轻叹道。
「那悲叹之种呢？」焰的语气中还带着一丝希望。
圆沉默不语，望着天空，只是无奈地摇了摇头。
「是吗...... 我说，我们就这样一起变成怪物，把这世界的一切都搞得一团糟吧。」焰说着，不由地啜泣起来。「把那些讨厌的事和悲伤的事，全都和没发生过一样，破坏掉、破坏掉、破坏殆尽...... 你不觉得，这样也很好吗？」
随着一声清脆的碰撞，焰感觉到魔力流入了自己的灵魂宝石内。她转头看见圆正微笑着，拿着一枚悲叹之种。
「刚才那是骗你的，」圆的笑容依旧那么甜美，「我还留着一个呢。」
焰慌忙抱住了圆的手臂，问到：「为什么，为什么要给我？」
「因为有件我做不到，但是小焰能做到的事，我想拜托你...... 小焰，你可以回到过去对吧？你说过，为了避免这样的结局，而改写过历史的吧......」
「嗯...」
圆也终于忍不住悲伤，晶莹的泪珠从她脸上滑落。「你能去救救那个还没被丘比欺骗的，笨蛋的我吗？」
**「我答应你，一定会救你的！无论重复多少次，我都会保护好你！」**
「太好了......」圆平静了下来，但下一瞬间，她的灵魂宝石中就散出了黑雾，她的表情也痛苦地扭曲了起来。「再......拜托你一件事可以吗？」
焰轻轻点头答应。
「我，不想变成魔女......」圆的声音更加虚弱，「就算有讨厌的事和悲伤的事，但我想守护的东西，在这世上还有很多。」圆艰难地抬起手臂，支撑着手中漆黑的灵魂宝石。
「小圆......」焰拔出手枪，对准了圆的灵魂宝石。在焰的痛哭声中，她扣下了扳机。
题目描述
澪正陪着铃一起 N 刷《魔法少女小圆》，看到全剧最催人泪下的情节之一时，家长却突然推门进来了。澪不想被发现自己在摸鱼，就迅速切换界面，假装她们在做一道计数题：
> 定义一棵有标号、有根、不区分左右儿子的二叉树的权值是：以「根节点的所有儿子节点」为根的子树的权值之和加上 $d$，特别定义只有一个节点的树权值为 $1$。求所有 $n$ 个节点的这种树权值的 $k$ 次方和，答案对 $998244353$ 取模。
「这不是那个什么 [NaCly_Fish's Math Contest](https://www.luogu.com.cn/contest/53104) 的题... 吗？」铃看了看题，小声说道，「好无聊哦，不看这题。」
输入输出格式
输入格式
输入一行三个正整数 $n,k,d$。
输出格式
输出一行一个整数，表示答案。
输入输出样例
输入样例 #1
3 0 2输出样例 #1
9输入样例 #2
3 2 2输出样例 #2
198输入样例 #3
4 3 2输出样例 #3
16008输入样例 #4
6 4 2输出样例 #4
58351320输入样例 #5
514 250 114输出样例 #5
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$。