Calculate the number of valid bracket sequences of length n.
For example, when n=6, there are 5 sequences:
One integer n (1≤n≤106).
Print the number of sequences modulo 109+7.