CF852F Product transformation

给定一个长度为 $N$ 的数组 $A$，其中所有元素均为同一个整数 $a$。 定义一次乘积变换为同时执行 $A_i = A_i \cdot A_{i+1}$，即将每个元素与其右侧的元素相乘，对于 $1 \leq i < N$，最后一个数 $A_N$ 保持不变。例如，若初始数组 $A$ 中 $a=2$ 且 $N=4$，则经过一次乘积变换后 $A = [4,\,4,\,4,\,2]$，经过两次乘积变换后 $A = [16,\,16,\,8,\,2]$。 你的任务是计算经过 $M$ 次乘积变换后的数组 $A$。由于数值可能非常大，输出时需对 $Q$ 取模。

输入仅一行，包含四个整数 $N$、$M$、$a$、$Q$（$7 \leq Q \leq 10^9+123$，$2 \leq a \leq 10^6+123$，$2 \leq N,M \leq 10^6+123$，$\operatorname{ord}_Q(a)$ 是质数，$N < \operatorname{ord}_Q(a) \leq 10^6+123$），其中 $\operatorname{ord}_Q(a)$ 是整数 $a$ 在模 $Q$ 意义下的乘法阶，定义见提示。

请从左到右输出数组 $A$。

一个数 $a$ 在模 $Q$ 下的乘法阶 $\operatorname{ord}_Q(a)$，是使得 $a^x\bmod Q=1$ 的最小正整数 $x$。例如，$\operatorname{ord}_7(3)=6$，因为 $3^6\equiv 1 \pmod{7}$。 由 ChatGPT 5 翻译