该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

题目描述

左侧有 N 个接线柱，右侧也有 N 个接线柱。

现在让你在接线柱之间连接若干导线。导线有黑、白两种颜色。

要求：

（1）每次连线，你需要从左、右两侧各选一个接线柱，在二者之间连接一条导线。

（2）两个接线柱之间至多连一条导线。

（3）任意一个接线柱上不能同时连接两条或两条以上同颜色的导线。

只要满足上述要求，你可以选择连接任意条导线。

当然，你也可以一条导线也不连接，这也算作一种连接方案。

问：你有多少种不同的连接方案？

答案可能很大，你需要输出答案 mod $(10^{9}+7)$。

输入格式

一个正整数 N

输出格式

一个整数，表示答案。

样例输入1

1

样例输出1

3

样例解释1

假设蓝色为接线柱，则有以下三种连线方案：

样例输入2

2

样例输出2

35

样例输入3

123456

样例输出3

108474174

数据规模

1 ≤ N ≤ 10^7