Capybara Cozy Carnival Cake Coloring

At the Capybara Cozy Carnival, chairman capybara is slicing a convex cake (a regular n-gon) with m continuous, non‐intersecting diagonal cuts. These cuts divide the cake into m+1 slices. The cake's corners are to be colored using one of k colors. However, the capybaras insist that neighboring corners in every slice must have contrasting colors. Two corners are defined as neighbors if they are consecutive in the original cyclic order of the cake or if they are the endpoints of one of the diagonal cuts.

More formally, label the vertices of the n-gon in cyclic order as 1,2,…,n. In addition to the cyclic edges between consecutive vertices (with an edge between n and 1), there are m extra edges (the cuts) which are drawn in a continuous (fan‐like) manner from vertex 1 to vertices 3,4,…,m+2. (It can be shown that these m cuts divide the cake into m+1 slices.) You are to count the number of ways to assign a color to each vertex from a palette of k colors such that:

• Any two consecutive vertices in the cyclic order have different colors.
• For every cut (an edge from 1 to i where 3 ≤ i ≤ m+2), the color at vertex 1 is different from the color at vertex i.

Since the number of valid colorings can be very large, output the answer modulo \(998\,244\,353\).

Note: The input consists of a single test case. It is guaranteed that n ≥ m+2.

inputFormat

The input is a single line containing three space‐separated integers: n, m, and k, where n is the number of vertices of the polygon (cake corners), m is the number of diagonal cuts (with m+1 slices), and k is the number of available colors.

outputFormat

Output a single integer—the number of valid colorings modulo \(998\,244\,353\).

sample

3 0 3

6