[语言月赛 202403] 传染病

新型病毒正在肆虐洛谷。

91-DIVOC 正在广泛传播，珂学家 RyanLi 想要探究 91-DIVOC 的传染系数。 第一天有 $a$ 个人被 91-DIVOC 感染，从第二天起，每个感染者都会向 $q$ 个没有感染的人传播 91-DIVOC，使他们变为感染者。 举个例子，如果第一天有 $3$ 人被感染，每个感染者每天向 $2$ 个人传播病毒，那么第二天会有 $3 \times 2$ 个人被感染。第三天会有 $3\times 2\times 2$ 个人被感染 $\cdots$ 以此类推。 定义传染系数为每天被感染 91-DIVOC 的人数的乘积，RyanLi 需要你求出 $k$ 天内的传染系数。由于这个数很大，你只需要输出它对 $722733748$ 取模的结果。

输入一行三个整数 $k,a,q$。

输出一行一个整数，表示答案。

3 3 2

216

### 数据规模与约定 对于 $20\%$ 的数据，$k \leq 7$，$a=2$，$q=2$。 对于 $50\%$ 的数据，$k \leq 10^3$。 对于 $100\%$ 的数据，$1 \leq k \leq 10^6$，$1 \leq a,q < 722733748$。