Bipartite Graph Counting

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

题目描述

一个班级男生女生数目相同都为 $n$ 。每对男女之间要么互相不认识，要么互相吸引，要么互相排斥。并且互相吸引的一对男女中男方和女方都不再和其他男女互相吸引（但可以互相排斥），互相排斥的一对男女中男方和女方都不再和其他男女互相排斥（但可以互相吸引）。计算有多少种可能的状态，并对 $1000000007$ 取模。

输入描述:

数目( ≤ )

输出描述:

输出一个整数,即所求的答案。

示例1

输入

复制

输出

复制

说明

4条边，任意两条相邻的边状态不能同时为互相吸引，或者同时为互相排斥.