Balance (1) P92795


Statement
 

pdf   zip

html

Given n weights 20, 21, …, 2n−1, we have to place all the weights on a balance, one after another, in such a way that the right pan is never heavier than the left pan. Please compute the number of ways of doing this.

For example, for n = 2 there are exactly three ways: placing first 2 on the left pan and then 1 on the right pan, placing first 2 on the left pan and then 1 on the left pan, and placing first 1 on the left pan and then 2 on the left pan. Note that, for instance, placing first 1 on the right pan and then 2 on the left pan is an incorrect way, since after placing 1 the right pan is heavier than the left pan.

Input

Input consists of several cases, each with a natural number 1 ≤ n ≤ 106.

Output

For every case, print the number of correct ways modulo 109 + 7.

Observation

This problem is basically problem 4 of IMO 2011.

Public test cases
  • Input

    1
    2
    3
    1000000
    

    Output

    1
    3
    15
    386044009
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++