BALKAN-SL 2011 N1

Given an odd number $n >1$ , let \begin{align*} S ={ k \mid 1 \le k < n , \gcd(k,n) =1 } \end{align*} and let \begin{align*} T = { k \mid k \in S , \gcd(k+1,n) =1 } \end{align*} For each $k \in S$ , let $r_k$ be the remainder left by $\frac{k^{|S|}-1}{n}$ upon division by $n$ . Prove \begin{align*} \prod {k \in T} \left( r_k - r{n-k} \right) \equiv |S| ^{|T|} \pmod{n} \end{align*}