Summing Powers of Tree Weights

We are given three integers n, d and k. Consider all labeled, rooted binary trees with n nodes (each node has at most two children) in which the left and right children are not distinguished (that is, swapping the two children gives the same tree). The weight of a tree is defined recursively as follows:

• If the tree consists of a single node then its weight is 1.
• If the tree has more than one node then let the weight of each subtree rooted at each child of the root be computed; the weight of the tree is defined as the sum of these weights plus d. In other words, if a node has one child with weight x then its weight is x+d, and if it has two children with weights x and y then its weight is x+y+d.

Your task is to compute the sum of the kth power of the weights of all such trees with n nodes, modulo 998244353.

Note that when constructing the trees the nodes are labeled with distinct labels from 1 to n. In the process of forming the tree the labeling gives additional combinatorial factors. In particular:

• For a tree with one child, the number of trees is n × (number of trees on n-1 nodes).
• For a tree with two children, suppose the two subtrees have sizes i and n-1-i (with i ≥ 1 and n-1-i ≥ 1). The labels (except the root) must be partitioned into two subsets (of sizes i and n-1-i). Since the two children are unordered, a 1/2 factor is introduced.

Formally, if we denote by W(T) the weight of a tree T, you need to compute

$$ \sum_{T}\; W(T)^k \bmod 998244353 $$

where the sum is taken over all labeled, rooted binary trees with n nodes as described.

inputFormat

The input consists of a single line containing three space‐separated integers: n, d and k.

Constraints (for example):

• 1 ≤ n ≤ 50
• 0 ≤ d ≤ 10⁹
• 0 ≤ k ≤ 50

outputFormat

Output a single integer which is the sum of the kth power of the weights of all trees with n nodes, modulo 998244353.

sample

1 5 3

1