题目描述
Problem Background
In a city reduced to ruins, a torrential rain pours down.
After defeating the "Witch's Night," Madoka and Homura are both severely injured and incapacitated due to lack of magic.
"We're finished..." Madoka sighs lightly.
"What about the Grief Seed?" Homura's voice carries a glimmer of hope.
Madoka remains silent, gazing at the sky, and simply shakes her head helplessly.
"Is that so... I said, let's just turn into monsters together and mess up everything in this world." Homura says, unable to hold back her tears. "To destroy all those annoying and sad things, as if they never happened, destroy them all... don't you think that would be good?"
With a crisp collision, Homura feels magic flowing into her Soul Gem. She turns to see Madoka smiling, holding a Grief Seed.
"I was just kidding," Madoka's smile remains sweet, "I still have one left."
Homura hurriedly grabs Madoka's arm and asks, "Why, why give it to me?"
"Because there's something I can't do, but Homura can. I want to ask you... Homura, you can go back in time, right? You said you've rewritten history to avoid this outcome..."
"Yeah..."
Madoka finally can't hold back her sadness, and tears roll down her cheeks. "Can you save that foolish me who hasn't been deceived 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 calms down, but the next moment, black mist emanates from her Soul Gem, and her expression twists in pain. "Can I ask you one more thing?"
Homura nods gently in agreement.
"I don't want to become a witch..." Madoka's voice grows weaker, "Even with annoying and sad things, there are still many things in this world that I want to protect." Madoka struggles to lift her arm, supporting the black Soul Gem in her hand.
"Madoka..." Homura draws her gun and aims at Madoka's Soul Gem. Amidst Homura's sobs, she pulls the trigger.
Problem Description
Mio is watching "Puella Magi Madoka Magica" for the Nth time with Rin, when their parents suddenly enter the room. Mio doesn't want to be caught slacking off, so she quickly switches to a different interface, pretending they are working on a counting problem:
Define the value of a labeled, rooted, non-distinguishing binary tree as the sum of the values of the subtrees rooted at all child nodes of the root plus $d$, with the special definition that a tree with only one node has a value of $1$. Calculate the sum of the $k$-th powers of the values of all such trees with $n$ nodes, modulo $998244353$.
"Isn't this the problem from the NaCly_Fish's Math Contest?" Rin murmurs after glancing at the problem, "How boring, let's not look at this."
Input Format
Input consists of three positive integers $n, k, d$.
Output Format
Output a single integer, the answer.
Sample Input and Output
Input Sample #1
3 0 2
Output Sample #1
9
Input Sample #2
3 2 2
Output Sample #2
198
Input Sample #3
4 3 2
Output Sample #3
16008
Input Sample #4
6 4 2
Output Sample #4
58351320
Input Sample #5
514 250 114
Output Sample #5
354914151
Notes
Explanation of Sample 1
There are $9$ labeled rooted binary trees with $3$ nodes, as shown below, with the red nodes indicating the roots.
Since $k=0$, the sum of the $k$-th powers of the tree values equals the total number of trees, hence the answer is $9$.
Explanation of Sample 2
Continuing from the previous diagram, the trees in the first row all have a value of $5$, and the trees in the second row have a value of $4$, so the answer is $6 \times 5^2 + 3 \times 4^2 = 198$.
Data Range
This problem uses subtask testing.
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): No special restrictions.
For $100\%$ of the data, $2 \le n, d \le 9 \times 10^8$, $0 \le k \le 5 \times 10^6$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分