Pairing Bottles

You are given three integers \(n\), \(D\) and \(m\). Consider a sequence of \(n\) integers, each chosen independently and uniformly at random from the range \([1, D]\). For a fixed outcome, let \(c_i\) be the number of times the integer \(i\) appears, for \(1 \le i \le D\). In a "bottling" scheme you are allowed to select some of these \(n\) variables, and then distribute each selected variable into a bottle so that every bottle contains exactly two variables having the same value. In other words, each bottle corresponds to a pair of equal integers (and an integer may be used in at most one bottle).

Your task is to calculate the probability (over all \(D^n\) outcomes) that there exists a way to form at least \(m\) such bottles (i.e. at least \(m\) pairs can be formed from the multiset \(\{c_1, c_2, \dots, c_D\}\)). Equivalently, if for an outcome we define \[ P = \sum_{i=1}^{D} \left\lfloor \frac{c_i}{2} \right\rfloor, \] then the outcome is favorable if \(P \ge m\).

Since the probability is a rational number with denominator \(D^n\), please output the value of the probability multiplied by \(D^n\) modulo \(998244353\). That is, if the number of favorable outcomes is \(X\), you should output \(X \bmod 998244353\).

Note: It is guaranteed that the modulo explanation is the same as in the first problem.

inputFormat

The input consists of a single line containing three integers \(n\), \(D\) and \(m\) separated by spaces.

\(n\): the number of randomly generated integers.\ \(D\): the maximum value of each integer (the integers are drawn from \([1, D]\)).\ \(m\): the minimum number of bottles (pairs) that need to be formed.

outputFormat

Output a single integer: the number of favorable outcomes multiplied by \(1\) (i.e. the probability multiplied by \(D^n\)), taken modulo \(998244353\).

sample

4 2 1

16