题目描述

求长度为$n$（$n\ge2$且n是偶数）的，由"()[]{}"六种字符组成，并且合法的括号匹配序列数量。答案对$10^9+7$取模。

合法规则：

1. 空串是合法的。
2. 如果字符串$P$是合法的，那么($P$)，[$P$]，{$P$}也是合法的。
3. 如果$P$，$Q$是合法的，那么P$$Q也是合法的。

输入描述

一行，一个正整数$n$，表示字符串的长度

样例

样例1输入：4 样例1输出：18

样例2输入：6 样例2输出：135

时间限制：1000ms

内存限制：128MB

这题不是luogu上的