题目描述

Smart 兼职小学老师赚钱。
他带的班里有 \(n\) 对双胞胎，编号为 \(1,2,…,n\)，他们排成一个长度为 \(2n\) 的队伍外出游玩。由于双胞胎间存在奇妙的联系，他们希望每对双胞胎之间隔开的人数正好等于这对双胞胎的编号。带队老师 Smart 对这个要求感到非常头疼，于是他请你来帮他计算一下满足这个要求的方案数。

格式

输入格式

输入仅一行，一个正整数 \(n\)。

输出格式

一个正整数，表示方案数 \(\text{mod}\) \(1000000007\) 的值。

样例1

样例输入1

3

样例输出1

2

样例解释

\(n=3\) 时，有两种方案：\(3,1,2,1,3,2\) 和 \(2,3,1,2,1,3\)。

限制

对于 \(30\%\) 的数据 \(n ≤ 8\)；
对于 \(50\%\) 的数据 \(n ≤ 12\)；
对于 \(100\%\) 的数据 \(n ≤ 18\)。