Задача №3006. Количество ПСП, где внутри квадратных скобок нет круглых

По данному натуральному n определите количество правильных скобочных последовательностей длины 2n, составленных из круглых и квадратных скобок так,что внутри любой пары круглых скобок нет квадратных скобок..

Входные данные

Программа получает на вход натуральное число n, не превосходящее 1000.

Выходные данные

Необходимо вывести остаток от деления числа искомых последовательностей на 109+7.

Примеры
Входные данные
1                           
Выходные данные
2
Входные данные
2 
Выходные данные
7
Сдать: для сдачи задач необходимо войти в систему