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

题目描述

平面上有 2n 条两两相交且不重合的直线，且任意三条直线不交于同一点；用红、蓝两色给交点染色，若一条直线上的红交点个数多于蓝交点个数，则该直线为红线，反之则为蓝线；对于给定的正整数 n，计算使得任意两条红线的交点不为蓝点且任意两条蓝线的交点不为红点的染色方法种数。由于答案可能会很大，请将答案对 1000000007 取模后输出。

输入描述:

一个正整数 n。

输出描述:

一个正整数表示答案，答案对 1000000007 取模。
示例1

输入

复制 
1

输出

复制 
2

说明

样例 1：显然当 n=1 的时候只有两种方案.

示例2

输入

复制 
2

输出

复制 
46

说明

样例 2：由下图所示，当 n=2 时有 34+12=46 种方案.

示例3

输入

复制 
15

输出

复制 
391969020

备注:

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