Given a positive integer $n$. An inversion of a permutation is the amount of pairs $(i,j)$ such that $i<j$ and the $i$-th number is smaller than $j$-th number in the permutation. Prove that for every positive integer $k \leq n$ there exist exactly $\frac{n!}{k}$ permutations in which the inversion is divisible by $k$.