Putnam 2008 B6

Let $n$ and $k$ be positive integers. Say that a permutation $\sigma$ of $\{1,2,\dots,n\}$ is $k$-limited if $|\sigma(i) - i| \leq k$ for all $i$. Prove that the number of $k$-limited permutations of $\{1,2,\dots,n\}$ is odd if and only if $n \equiv 0$ or $1$ (mod $2k+1$).