I've been playing with Fourier transform a little and discovered the identity quoted in the title. More precisely, writing the matrix for the Fourier transform in ${\mathbb Z} / N {\mathbb Z}$ as
$A = {1 \over \sqrt{N}} \pmatrix{ \zeta^0& \zeta^0 & \cdots & \zeta^0 \cr \zeta^0& \zeta^1 & \cdots & \zeta^{N-1} \cr \vdots & \vdots &\ddots &\vdots \cr \zeta^0& \zeta^{N-1} & \cdots & \zeta^1 \cr }$
(with $\zeta \equiv \exp({2 \pi i \over N})$) one easily obtains the quoted identity by using the famous determinant of Vandermonde matrix and the fact that the transform is unitary.
Now, I'd be interested whether the identity can be proven directly, and ideally given a nice combinatorial interpretation. I suppose this should be possible because of lot of structure in the problem but I wasn't able to come up with anything yet.