Paradoxical tests P89942


Statement
 

pdf   zip

html

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?
  1. 2/5
  2. 3/5
  3. 3/5
  4. 2/5
  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