Кількість ПДП

Обчисліть кількість правильних дужкових послідовностей довжини 2n (n відкриваючих дужок та n закриваючих), склдених з круглих та квадратних дужок так, что всередині довільної пари круглих дужок немає квадратних дужок.

Вхідні дані

У єдиному рядку записано ціле невід'ємне число n, яке не перевищує 1000.

Вихідні дані

Виведіть залишок від ділення кількості шуканих правильних дужкових послідовностей на 10^9+7.

Приклади