Kata

Note:  The problem is identical to raulbc777's kata Shuffle It Up but with slightly more challenging tests.

Problem Statement

Assume we have a list of n elements: [1, 2, 3, ..., n].

The task is to compute the number of ways to rearrange the elements such that no element remains in its initial position.

As input we are given the number of elements N, a positive integer. Since the answer grows rather quickly as n increases, we compute the answer modulo 1,000,000,007.

Example

Input: n = 3   =>   [1, 2, 3]

There are two ways of rearranging the elements of [1, 2, 3] such that no element is in its original position:

[2, 3, 1], [3, 1, 2]   =>   return 2

See the sample tests for more examples.

Input/Output

Input:  a positive integer 1 <= n <= 8,000,000.

Output:  also an integer, as specified in the problem statement above.

The input will always be an integer in the given range, no need to handle bad input.