考虑一个具有 N 个元素的数组 A,所有元素都是相同的整数 a。
将乘积转换定义为同时更新 Ai = Ai·Ai + 1,即将每个元素与其右侧的元素相乘 $$i \in (1, 2,..., N-1)$$,最后一个数字 AN 保持不变。例如,如果我们从 a = 2 且 N = 4 的数组 A 开始,则在一次乘积转换后 A = [4, 4, 4, 2],在两次乘积转换后 A = [16, 16, 8, 2]。
您的简单任务是在 M 次乘积转换后计算数组 A。由于数字可能变得相当大,因此您应该以 Q 为模输出它们。
输入
输入的第一行也是唯一一行包含四个整数 N、M、a、Q(7 ≤ Q ≤ 109 + 123、2 ≤ a ≤ 106 + 123、$$1 \leq M、N < \phi(a, Q) \leq 10^6 + 123$$、$$\phi(a,Q)$$ 是质数),其中$$\phi(a,Q)$$ 是整数 a 模 Q 的乘法阶,定义见注释。
输出
你应该从左到右输出数组A。
示例
输入 #1
2 2 2 7
输出 #1
1 2
注意
数字 a 模 Q $$\phi(a,Q)$$ 的乘法阶是满足 ax mod Q = 1 的最小自然数 x。例如,$$\phi(2,7)=3$$。