题目背景

新型病毒正在肆虐洛谷。

题目描述

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$。