P8560 Promise

In a city turned into ruins, heavy rain poured down. After “Walpurgis Night” was defeated, Madoka and Homura were also covered in wounds and collapsed because they had run out of magic power. “We... are finished too...” Madoka sighed softly. “What about the Grief Seed?” Homura’s voice still carried a bit of hope. Madoka said nothing. She looked up at the sky and could only shake her head helplessly. “I see... Then, I mean, let’s just become witches together and mess everything in this world up.” As Homura spoke, she could not help but sob. “Destroy all those hateful things and sad things, as if they never happened. Destroy, destroy, destroy it all... Don’t you think that’s fine too?” With a crisp clink, Homura felt magic power flow into her Soul Gem. She turned her head and saw Madoka smiling, holding a Grief Seed. “That was a lie just now,” Madoka’s smile was still as sweet as ever. “I kept one.” Homura hurriedly hugged Madoka’s arm and asked, “Why, why are you giving it to me?” “Because there is something I can’t do, but you can, Homura-chan. I want to ask you...” Madoka said. “Homura-chan, you can go back to the past, right? You said you rewrote history to avoid an ending like this...” “Yeah...” Madoka finally could not hold back her sadness either, and clear tears slid down her face. “Can you go and save that stupid me, the one who hasn’t been tricked by Kyubey yet?” **“I promise you, I will definitely save you! No matter how many times it takes, I will protect you!”** “That’s great...” Madoka calmed down, but in the next moment, black mist spread out from her Soul Gem, and her expression twisted in pain. “Can I... ask you one more thing?” Homura nodded gently. “I... don’t want to become a witch...” Madoka’s voice grew even weaker. “Even if there are hateful things and sad things, there are still many things I want to protect in this world.” Madoka struggled to raise her arm, supporting the pitch-black Soul Gem in her hand. “Madoka...” Homura pulled out her pistol and aimed at Madoka’s Soul Gem. Amid Homura’s painful crying, she pulled the trigger. #

Mio was watching *Puella Magi Madoka Magica* with Rin for the $N$-th time. When they reached one of the most tear-jerking scenes in the whole show, their parents suddenly pushed the door open. Mio did not want to be caught slacking off, so she quickly switched the window and pretended they were doing a counting problem: > Define the weight of a labeled, rooted, left-right-unordered binary tree as: the sum of the weights of the subtrees rooted at “all children of the root node”, plus $d$. In particular, define the weight of a tree with only one node as $1$. Compute the sum of the $k$-th powers of the weights over all such trees with $n$ nodes. Output the answer modulo $998244353$. “Isn’t this that problem from [NaCly_Fish's Math Contest](https://www.luogu.com.cn/contest/53104) ...?” Rin looked at the statement and whispered, “So boring. I’m not reading this problem.”

One line with three positive integers $n,k,d$.

One line with one integer, the answer.

[Sample $1$ Explanation] There are $9$ labeled rooted binary trees with $3$ nodes, as shown below. The red node indicates the root.  Since $k=0$, the sum of the $k$-th powers of all tree weights equals the total number of trees, so the answer is $9$. [Sample $2$ Explanation] Continuing from the figure above: the weights of the trees in the first row are all $5$, and the weights of the trees in the second row are $4$, so the answer is $6\times 5^2+3\times 4^2=198$. [Constraints] **This problem uses bundled testdata.** Subtask 1 (5 pts): $n \le 6$. Subtask 2 (9 pts): $k=0$, $n\le 10^7$. Subtask 3 (14 pts): $n\le 10^5$. Subtask 4 (18 pts): $k \le 4000$, $n\le 10^7$. Subtask 5 (23 pts): $k \le 10^5$. Subtask 6 (31 pts): no special constraints. For $100\%$ of the data, $2\le n,d \le 9\times 10^8$, $0\le k \le 5\times 10^6$. Translated by ChatGPT 5