Rhyme Assignment

You are given a task to write a song with exactly (n \times d) characters. You have designed (k) types of rhymes, and every character in the song must be assigned exactly one rhyme. The song will sound good only if for every rhyme, the number of characters assigned to it is a multiple of (d).

In other words, if we denote by (x_i) the number of characters with the (i\text{-th}) rhyme, then (x_i) is a multiple of (d) for every (i) (i.e. (x_i = d \times y_i) for some nonnegative integer (y_i)), and (\sum_{i=1}^{k} x_i = n \times d). This reduces to (\sum_{i=1}^{k} y_i = n).

The number of solutions (i.e. ways to assign the rhymes) is given by the stars and bars formula [ {n+k-1 \choose k-1} ]

Output the number of such assignments modulo (1049874433).

inputFormat

The input consists of three integers (n), (k), and (d) separated by spaces.

outputFormat

Output a single integer: the number of valid rhyme assignments modulo (1049874433).

sample

3 2 2

4