题目描述

叉地萌舞是一款风靡一时的音乐街机游戏。这款游戏的屏幕是一个正方形，被分成了 $(2n + 1) \times (2n + 1)$ 个格子。这就是说，这款游戏的屏幕被平分成了 $(2n + 1)$ 行，每行都由 $(2n + 1)$ 个大小相等的排成一行的小正方形组成，每个小正方形是一个格子。下图是一个 $n = 2$ 时屏幕分区的示例：

你是一名叉地萌舞的谱师，你要在这个屏幕上绘制一个名为幻灯片（slide）的音符。这个音符在屏幕最中心的格子（上图中蓝色星星标记的格子）出发，初始时前进方向朝向右。接下来，这个音符会朝着前进方向前进一个格子。在音符每次前进之后，你可以选择将音符的朝向逆时针旋转 90°。音符最终必须停止在最右上角（上图中红色星星标记的格子）。

显然，音符构成的轨迹是一条覆盖了若干个格子的路径。我们称一条路径是有理的当且仅当每个格子至多被路径覆盖了一次。例如，下图是一个有理的路径：

需要注意的是，每次音符前进后，你只能逆时针转动音符前进方向至多一次，因此如下图所示不能被称为一个路径：

通俗地说，音符只能直行或左转，不能右转。

给定 $n$，你需要计算有理的路径条数。因为答案可能很大，你需要输出答案除以 $10 ^ 9 + 7$ 的余数。

输入格式

输入只有一行一个整数，表示 $n$。

输出格式

输出一行整数表示答案。

样例

样例输入 1

2

样例输出 1

9

样例输入 2

1000

样例输出 2

696552643

数据规模与约定

本题共 $10$ 个测试点，每个测试点 $10$ 分。

对全部的测试数据，保证 $1 \leq n \leq 10^5$。