#1801. [语言月赛 202403] 传染病

[语言月赛 202403] 传染病

题目描述

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

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

举个例子,如果第一天有 33 人被感染,每个感染者每天向 22 个人传播病毒,那么第二天会有 3×23 \times 2 个人被感染。第三天会有 3×2×23\times 2\times 2 个人被感染 ⋯\cdots 以此类推。

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

输入格式

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

输出格式

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

样例

3 3 2
216

题目来源:洛谷 B3944