Дискретное преобразование Фурье - 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 означает взятие остатка по модулю.

Input

В первой строке входных данных записано пять целых чисел: n, X, Y, Z, T (1 ≤ n ≤ 10^7, 1 ≤ X, Y, Z, T ≤ 10^6).

Output

Выведите единственное число c относительной или абсолютной погрешностью не превышающей 10^{-6}, где real() означает действительную часть, а imag() — мнимую.

Examples