{"raw_statement":[{"iden":"background","content":"新型病毒正在肆虐洛谷。"},{"iden":"statement","content":"91-DIVOC 正在广泛传播，珂学家 RyanLi 想要探究 91-DIVOC 的传染系数。\n\n第一天有 $a$ 个人被 91-DIVOC 感染，从第二天起，每个感染者都会向 $q$ 个没有感染的人传播 91-DIVOC，使他们变为感染者。\n\n举个例子，如果第一天有 $3$ 人被感染，每个感染者每天向 $2$ 个人传播病毒，那么第二天会有 $3 \\times 2$ 个人被感染。第三天会有 $3\\times 2\\times 2$ 个人被感染 $\\cdots$ 以此类推。\n\n定义传染系数为每天被感染 91-DIVOC 的人数的乘积，RyanLi 需要你求出 $k$ 天内的传染系数。由于这个数很大，你只需要输出它对 $722733748$ 取模的结果。"},{"iden":"input","content":"输入一行三个整数 $k,a,q$。"},{"iden":"output","content":"输出一行一个整数，表示答案。"},{"iden":"note","content":"### 数据规模与约定\n\n对于 $20\\%$ 的数据，$k \\leq 7$，$a=2$，$q=2$。  \n对于 $50\\%$ 的数据，$k \\leq 10^3$。  \n对于 $100\\%$ 的数据，$1 \\leq k \\leq 10^6$，$1 \\leq a,q < 722733748$。"}],"translated_statement":null,"sample_group":[["3 3 2","216"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}