题目描述

新型病毒正在肆虐洛谷。

91-DIVOC 正在广泛传播，珂学家 RyanLi 想要探究 91-DIVOC 的传染系数。

第一天有 $a$ 个人被 91-DIVOC 感染，从第二天起，每个感染者都会向 $q$ 个没有感染的人传播 91-DIVOC，使他们变为感染者。

举个例子，如果第一天有 $3$ 人被感染，每个感染者每天向 $2$ 个人传播病毒，那么第二天会有 $3\times 2$ 个人被感染，第三天会有 $3\times 2\times 2$ 个人被感染，以此类推。

定义传染系数为每天被感染 91-DIVOC 的人数的乘积，RyanLi 需要你求出 $k$ 天内的传染系数。由于这个数很大，你只需要输出它对 $722733748$ 取模的结果。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3 3 2

样例输出 #1

216

提示

样例解释

三天分别感染 $3,6,12$ 人，乘积 $3\times 6\times 12=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$。