이그렉과 괄호 트리

모두가 알다시피 픽시키 중에서 이그렉이 학교에서 가장 똑똑하다. 그도 우리처럼 어려운 문제 푸는 것을 좋아한다. 최근 그는 트리, 그중에서도 괄호 트리에 관심을 갖게 되었지만, 생각보다 까다로웠다. 아래는 그가 풀지 못한 문제 중 하나다.

괄호 트리는 루트가 있는 트리다. 각 정점에는 여는 괄호 또는 닫는 괄호가 적혀 있다. 각 정점의 자식은 순서가 정해져 있고, 각 자식도 괄호 트리다.

$root_T$는 괄호 트리 $T$의 루트를, $a_v$는 정점 $v$에 적힌 괄호를 나타낸다.

두 괄호 트리 $A$와 $B$는 $root_A$와 $root_B$에 적힌 괄호가 같고, 두 루트의 자식 수가 같으며, 모든 $i$에 대해 $root_A$의 $i$번째 자식과 $root_B$의 $i$번째 자식이 동치일 때 동치라고 한다.

괄호 트리의 정점 $v$에 대해 다음과 같이 재귀 함수 $f(v)$를 정의한다.

$v$가 리프이면 $f(v)=a_v$이다.

그렇지 않으면 $f(v)=f(c_1)+f(c_2)+\dots+f(c_k)+a_v$이다. 여기서 $c_1, \dots, c_k$는 $v$의 자식을 순서대로 나열한 것이다.

이 함수의 결과는 여는 괄호와 닫는 괄호로 이루어진 문자열이다.

$f(root_T)$가 여는 괄호를 $n$개 가진 올바른 괄호 문자열이 되도록 하는 서로 다른 괄호 트리 $T$는 몇 개인가?

정수 $n$ ($1 \le n \le 10^5$)이 한 줄에 주어진다. 이는 $f$를 적용해서 얻은 괄호 문자열에 들어 있는 여는 괄호의 개수다.

답을 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.