2011 AIME II Problem 14

There are N permutations \left(a_{1}, a_{2}, \ldots, a_{30}\right) of 1,2, \ldots, 30 such that
for m \in \{2,3,5\}, m divides a_{n+m}-a_{n} for all integers n with 1 \leq n<n+m \leq 30. Find the remainder when N is divided by 1000 .