Discrete Fourier Transform - 2

In this problem, you are required to perform the Discrete Fourier Transform (DFT) of a polynomial. Recall that the Discrete Fourier Transform is the vector

where the coefficients are calculated by the following formula:

For simplicity, let us assume that a_0 = X, and for k \geq 1, the following holds: a_k = (Y a_{k-1} + Z) \mod T, where $X$, $Y$, $Z$, $T$ are given numbers, and \mod denotes the remainder after division.

Output

Print a single number with a relative or absolute error not exceeding 10^{-6}, where $\mathrm{real}()$ denotes the real part, and $\mathrm{imag}()$ denotes the imaginary part.