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