Diskret Furye çevrilməsi - 2

Bu tapşırıqda sizdən çoxhədli üçün diskret Furye çevrilməsini həyata keçirmək tələb olunur. Xatırladaq ki, diskret Furye çevrilməsi, əmsalları aşağıdakı düsturla hesablanan y = (y_0, y_1, ..., y_{n-1}) vektorudur:

Sadəlik üçün qəbul edək ki, a_0=X, və k=1-dən başlayaraq belədir: a_k = (Ya_{k-1}+Z) mod T, burada X, Y, Z, T - verilmiş ədədlərdir, və mod modula görə qalıq götürmə əməliyyatını ifadə edir.

Giriş verilənləri

Giriş məlumatlarının birinci sətirində beş tam ədəd yazılmışdır: n, X, Y, Z, T (1 ≤ n ≤ 10^7, 1 ≤ X, Y, Z, T ≤ 10^6).

Çıxış verilənləri

real() həqiqi hissəni, imag() isə xəyali hissəni ifadə etməklə, nisbi və ya mütləq xətası 10^{-6}-dan çox olmayan tək bir ədəd çıxarın.

Nümunələr