Define the discrete Fourier transform of a sequence $\left\{x_{0}, x_{1}, \ldots, x_{N-1}\right\}$ of $N$ complex numbers.

Compute the discrete Fourier transform of the sequence

$$x_{n}=\frac{1}{N}\left(1+e^{2 \pi i n / N}\right)^{N-1} \quad \text { for } n=0, \ldots, N-1 .$$