SP4202 BRPAR - Brackets Parade

Count the number of different correct bracket sequences consisting of k1 pairs of brackets of the 1st type, k2 pairs of brackets of the 2nd type, …, km pairs of brackets of the m-th type. The bracket sequence is considered correct in the following cases: - empty sequence is correct; - if A is correct and B is correct then AB is correct; - if A is correct then ( $ _{i} $ A) $ _{i} $ is correct where ( $ _{i} $ and ) $ _{i} $ are opening and closing brackets of the same type.

The first line of input is the number 0 < n

For each test case output a line containing single integer – the answer to the problem modulo 1000000007.