Дискретне перетворення Фур`є - 2

У цій задачі вам потрібно здійснити дискретне перетворення Фур'є для многочлену . Нагадаємо, що дискретне перетворення Фур'є - це вектор y = (y_0, y_1, ..., y_{n-1}), коефіцієнти якого обчислюються по формулі:

.

Для простоти будем вважати, що a_0=X, а починаючи з k=1, виконується: a_k = (Ya_{k-1}+Z) mod T, де X, Y, Z, T - задані числа, а mod позначає операцію взяття залишку по модулю.

Вхідні дані

У першому рядку вхідних даних записано п'ять цілих чисел: n, X, Y, Z, T (1 ≤ n ≤ 10^7, 1 ≤ X, Y, Z, T ≤ 10^6).

Вихідні дані

Виведіть єдине число з відносною чи абсолютною похибкою, яка не перевищує 10^{-6}, де real() позначає дійсну частину, а imag() — уявну.

Приклади