Задачи
Дискретное преобразование Фурье - 2
Дискретное преобразование Фурье - 2
\includegraphics{https://static.e-olymp.com/content/d0/d039aaa5a6ab4d239cf99ce0e8d757e8a893544b.jpg}
В этой задаче вам требуется провести дискретное преобразование Фурье для многочлена . Напомним, дискретное преобразование Фурье - это вектор \textbf{y = (y_0, y_1, ..., y_\{n-1\})}, коэффициенты которого вычисляются по формуле:
\includegraphics{https://static.e-olymp.com/content/93/9323e6ea35576332c6d3abf00d416a801c0a01e3.jpg}
.
Для простоты будем считать, что \textbf{a_0=X}, а начиная с \textbf{k=1}, выполнено: \textbf{a_k = (Ya_\{k-1\}+Z) mod T}, где \textbf{X}, \textbf{Y}, \textbf{Z}, \textbf{T} - заданные числа, а \textbf{mod} означает взятие остатка по модулю.
\InputFile
В первой строке входных данных записано пять целых чисел: \textbf{n}, \textbf{X}, \textbf{Y}, \textbf{Z}, \textbf{T} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^7}, \textbf{1} ≤ \textbf{X}, \textbf{Y}, \textbf{Z}, \textbf{T} ≤ \textbf{10^6}).
\OutputFile
\includegraphics{https://static.e-olymp.com/content/94/94dbefa86e3c22de28ef5fc171093f7662bf81b2.jpg}
Выведите единственное число c относительной или абсолютной погрешностью не превышающей \textbf{10^\{-6\}}, где \textbf{real()} означает действительную часть, а \textbf{imag()} --- мнимую.
Входные данные #1
2 7 4 3 8
Выходные данные #1
14.0000000000