Domino铺设

题号：NC220777
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

我们称在一个 $2\times n$ 的点阵中画出 n 条不相交的线的方式，为一种 $2\times n$ 矩形的 “Domino铺设”，例如

，一个图案称为 “Domino铺设” 的条件是：各线均不相交、每条线要么竖直要么水平、每条线连接两个格点；
如果我们将两个这样的图案叠加起来，就得到一组回路，这是由于每点都与两条线相连，例如，如果上面的线与这样的线：

，组合起来，结果就是：

而且，将，

和

组合起来也会得到同一组回路。但是，如果在第一个图案中交替用向上、向下、向上、向下、…的红色箭头，在第二个图案中交替用向下、向上、向下、向上、…的蓝色箭头，为那些竖直的线指定方向，我们就会得到从叠加的图案中构造出定向回路的唯一一种方案，例如：

通过这样的设定，构造这种定向回路图案的方案数是确定的。换句话说，如果两个回路相同，当且仅当构成两个回路的铺设完全相同。

给定正整数 n ，求出在 $2\times n$ 的点阵中构造定向回路图案的方案数，由于结果可能特别大，所以输出答案对 1000000007 取模后的结果。

输入仅一行，一个正整数 n （） 。

输出一个数，表示方案数，结果对 1000000007  取模。

示例1

复制

复制

n=2，即  的点阵中构造定向回路的方案数显然只有 4 种：

示例2

复制

复制

n=3，即  的点阵中构造定向回路的方案数显然只有 9 种：

示例3

复制

复制

对于 60% 的数据，保证 ,
对于 100% 的数据，保证 .