*Problem #9*

Recall that a permutation *p* on the set {1,2,...,*n*} is
a function *p* from {1,2,...,*n*} to itself such
that no
two elements are mapped to the same element. Call a permutation *p*
an *equidistance permutation* if there is a constant *c* such
that |*p*(*i*) - *i*| = *c* for all *i* in
{1,2,...,*n*}. Find the number of equidistance permutations for
*n* = 1000000.
**Source: Weixuan Li and Edward T.H. Wang**