约定（Promise）

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