91-DIVOC Transmission Coefficient

RyanLi is studying the spread of 91-DIVOC. On the first day, a people are infected. Starting from the second day, every infected person infects q new people (who were not infected before), which makes them infected. For example, if 3 people are infected on day 1 and each infected person infects 2 people daily, then on day 2 there will be 3×2 infected people and on day 3 there will be 3×2×2 infected people, and so on.

The transmission coefficient is defined as the product of the number of people newly infected on each day over k days. Mathematically, if the number of infections on day i is given by \(a\) on day 1 and \(a\cdot q^{i-1}\) on day \(i\) (for \(i\ge 1\)), then the transmission coefficient \(T\) over k days is:

\[ T = \prod_{i=1}^{k} \Big(a \cdot q^{i-1}\Big) = a^{k} \cdot q^{0+1+2+\cdots+(k-1)} = a^{k} \cdot q^{\frac{k(k-1)}{2}}. \]

Since the number can be very large, output \(T\) modulo 722733748.

inputFormat

The input consists of a single line containing three integers a, q and k separated by spaces, where:

• a is the number of people infected on the first day,
• q is the number of people each infected person can infect each day (starting from day 2), and
• k is the number of days.

outputFormat

Output a single integer representing the transmission coefficient over k days modulo 722733748.

sample

3 2 3

216