题目背景

翻译自 CSES-2064 题。

题目描述

你的任务是计算长度为 $n$ 的有效括号序列的数量。例如，当 $n = 6$ 时，有 $5$ 种有效括号序列：

$$()()(), \, ()(()), \, (())(), \, ((())), \, (()()) $$

输入格式

唯一的输入行包含一个整数 $n$。

输出格式

输出有效括号序列的数量，结果对 $10^9+7$ 取模。

样例

6

5

说明/提示

$1 \leq n \leq 10^6$。