题目描述

某校第一天有 $a$ 个学生得知了一条新消息。从第二天开始，每个已经知情的学生都会向 $q$ 个尚不知情的学生传递这条消息，使他们也成为知情者。

例如，第一天有 $3$ 人知情，每人每天传给 $2$ 个新人，则第二天新增 $3 \times 2$ 人知情，第三天新增 $3 \times 2 \times 2$ 人知情，以此类推。

定义传播系数为连续 $k$ 天中，每天知情人数的乘积。具体来说，第 $i$ 天的知情人数为 $a \times q^{i-1}$，传播系数为 $\prod_{i=1}^{k} a \times q^{i-1}$。

请计算 $k$ 天的传播系数，并将结果对 $722733748$ 取模后输出。

输入格式

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

输出格式

一行一个整数，表示传播系数对 $722733748$ 取模的结果。

样例

3 3 2

216

提示

数据规模与约定

对于 $20\%$ 的数据，$k \le 7$，$a=2$，$q=2$。
对于 $50\%$ 的数据，$k \le 10^3$。
对于 $100\%$ 的数据，$1 \le k \le 10^6$，$1 \le a, q \lt 722733748$。