Consider the following test:

What is the probability that if you choose at random one answer of this test,
your answer will turn out to be correct?

- 2/5
- 3/5
- 3/5
- 2/5
- 3/5

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.

Public test cases

**Input**

1 3 5 203 1000

**Output**

0 3 15 1006132 707988

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Desè Concurs de Programació de la UPC - Semifinal
- Date
- 2012-06-30