Paradoxical tests P89942

Consider the following test:

As you can see, all answers above may be considered correct, but none of them is 1!

Given the number of answers $n$ of a test, how many such paradoxical tests exist? Note that the order of the answers is relevant. For instance, a test with d) $3/5$ and e) $2/5$ would be considered different to the one above.

Input

Input consists of several cases, each one with a number $n$ between 1 and 1000.

Output

For every $n$, print the number of paradoxical tests with $n$ answers modulo 1006133.