Sparkling Star Cluster

There is a star cluster in the sky that initially contains n stars (i.e. one cluster with n stars). Little K thinks that a single star cluster is not romantic enough, so she decides to use her magic. When casting the magic, for each cluster that currently contains a stars (with a \ge 2), she adds new clusters each containing 1, 2, \ldots, a-1 stars respectively. (Note that the original cluster is retained.)

The brilliance of a cluster with v stars is defined as \(k^{v}\). After performing the magic m times (i.e. m operations), output the sum of the brilliance of all clusters in the sky modulo \(998244353\).

Formal Statement:

Initially, you are given a multiset \(S_0\) containing one number \(n\). An operation is defined as follows: Create a new multiset \(S_1\). For every element \(a\) in \(S_0\) (if \(a \ge 2\)), for every \(j\) from \(1\) to \(a-1\), insert \(j\) into \(S_1\). At the end of the operation, add all elements of \(S_1\) into \(S_0\).

Let the brilliance of a cluster with v stars be \(k^v\). Compute \(\sum_{x \in S_0} k^{x}\) after m operations, modulo \(998244353\).

Example: For instance, if \(n = 3\), \(m = 1\) and an arbitrary \(k\) is given, initially \(S_0 = \{3\}\). After 1 operation, since the only cluster 3 (with 3 \(\geq\) 2) spawns clusters of sizes 1 and 2, the final multiset is \(\{3, 1, 2\}\) and the answer is \(k^3 + k^1 + k^2\) (modulo \(998244353\)).

inputFormat

The input consists of a single line containing three integers n, m, and k where:

• n is the number of stars in the initial (and only) cluster.
• m is the number of times the magic is cast.
• k is the base used in the brilliance function \(k^v\).

outputFormat

Output a single integer, the sum of the brilliance of all star clusters after m operations, modulo \(998244353\).

sample

3 1 2

14