Product transformation

题意翻译

有一个长度为n的数组A，开始时，A内的元素全为a。 现在进行m次操作，每次操作将A[i]变为A[i]*A[i+1]，最后一个元素不变。 现给出n,m,a,Q，输出m次操作后的A数组，每个元素对Q取模。 感谢@ObsdianGungnir 提供的翻译

题目描述

Consider an array $ A $ with $ N $ elements, all being the same integer $ a $ . Define the product transformation as a simultaneous update $ A_{i}=A_{i}·A_{i+1} $ , that is multiplying each element to the element right to it for , with the last number $ A_{N} $ remaining the same. For example, if we start with an array $ A $ with $ a=2 $ and $ N=4 $ , then after one product transformation $ A=[4,\ 4,\ 4,\ 2] $ , and after two product transformations $ A=[16,\ 16,\ 8,\ 2] $ . Your simple task is to calculate the array $ A $ after $ M $ product transformations. Since the numbers can get quite big you should output them modulo $ Q $ .

输入输出格式

输入格式

The first and only line of input contains four integers $ N $ , $ M $ , $ a $ , $ Q $ ( $ 7<=Q<=10^{9}+123 $ , $ 2<=a<=10^{6}+123 $ , ,  is prime), where  is the multiplicative order of the integer $ a $ modulo $ Q $ , see notes for definition.

输出格式

You should output the array $ A $ from left to right.

输入输出样例

输入样例 #1

2 2 2 7

输出样例 #1

1 2 

说明

The multiplicative order of a number $ a $ modulo $ Q $ , is the smallest natural number $ x $ such that $ a^{x}\ mod\ Q=1 $ . For example, .