29027번 - Игрек и скобочное дерево 다국어

문제

Все знают, что Игрек самый умный в фиксик в школе. Он, как и мы с вами, любит решать сложные задачки. Недавно он заинтересовался деревьями, а конкретно cкобочными деревьями, но они не так просты, как ему показалось сначала. Вот одна из задачек, которые он не смог решить.

Скобочное дерево --- это такое подвешенное дерево, в каждой вершине которого записана открывающая или закрывающая скобка, дети каждой вершины упорядочены, и каждый ребенок является скобочным деревом.

Обозначим корень скобочного дерева $T$ как $root_T$. За $a_v$ обозначим скобку, которая записана в вершине $v$.

Введем также отношение эквивалентности двух скобочных деревьев: два скобочных дерева $A$ и $B$ являются эквивалентными, если скобки, записанные в $root_A$ и $root_B$ равны, количество детей $root_A$ и $root_B$ одинаково и, наконец, $i$-й ребенок $root_A$ эквивалентен $i$-му ребенку $root_B$.

Введем рекурсивную функцию $f(v)$ от вершины скобочного дерева, которая будет вычисляться следующим образом:

• $f(v)=$
  • $a_v,ドル если $v$ лист
  • $f(c_1) + f(c_2) + \dots + f(c_k) + a_v,ドル где $c_i$ --- дети вершины $v$ в упорядоченном порядке

Результатом этой функции является строка из открывающих и закрывающих скобок.

Сколько существует различных скобочных деревьев $T,ドル таких что $f(root_T)$ является правильной скобочной последовательностью с $n$ открывающими скобками?

А вы сможете помочь Игреку с этой задачкой?

입력

В первой строке дано натуральное число $n$ (1ドル \le n \le 10^5$) --- количество открывающих скобок в скобочной последовательности, полученной в результате применения функции $f$.

출력

В единственной строке выведите ответ на задачу по модулю 10ドル^9+7$.

제한

힌트