Question 9
For every positive integer $n$ determine the number of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$ with the following property:
$$
2\left(a_{1}+a_{2}+\cdots+a_{k}\right) \quad \text { is divisible by } k \text { for } k=1,2, \ldots, n \text {. }
$$
$$
2\left(a_{1}+a_{2}+\cdots+a_{k}\right) \quad \text { is divisible by } k \text { for } k=1,2, \ldots, n \text {. }
$$