Some parenthesizations P31589


Statement
 

pdf   zip

thehtml

Given a natural number n, compute the number of correct parenthesizations with n opening and n closing parentheses, with just one restriction: the substring “)()” is not allowed.

For instance, for n = 4 there are four correct parenthesizations: “(((())))”, “(()(()))”, “(())(())” and “()((()))”.

Input

Input consists of several cases, each one with an n between 1 and 104.

Output

For each n, print the result modulo 109 + 7.

Public test cases
  • Input

    4
    1
    2
    3
    5
    10000
    

    Output

    4
    1
    1
    2
    9
    681928184
    
  • Information
    Author
    Xavier Povill
    Language
    English
    Official solutions
    C++
    User solutions
    C++