Рассмотрим массив A с N элементами, все из которых равны a.
Определим преобразование произведение как одновременное обновление элементов массива Ai = Ai·Ai + 1, которое умножает каждый элементы на элемент справа от него для 
, а последний элемент AN остаётся неизменным. Например, если мы начнём с массива A с a = 2 и N = 4, после первого преобразования произведения A = [4, 4, 4, 2], а после двух A = [16, 16, 8, 2].
Ваша простая задача — найти массив A после M преобразований произведения. Так как числа могут стать очень большими, выведите ответ по модулю Q.
Выходные данные
Выведите массив A слева направо, разделённый пробелами.
Примечание
Мультипликативный порядок числа a по модулю Q 
— это наименьшее положительное целое число x такое, что ax mod Q = 1. Например, 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 2 7
|
1 2
|