Derangements

A derangement is a permutation of 1..n in which no element stays in its original position. Print the number of derangements modulo 1,000,000,007.

1 <= n <= 10^6