考虑一个 $3 \times N$ 的规则点阵。点阵中的每个点最多有八个相邻的点（见图 1）。
图 1：相邻的点（用箭头标出）
我们希望计算有多少种不同的方法来连接点阵中的点，以形成一个满足以下条件的多边形：
- 多边形的顶点集由所有 $3 \times N$ 个点组成。
- 多边形中相邻的顶点在点阵中也是相邻的点。
- 每个多边形都是简单多边形，即不能有任何自交。
图 2 给出了 $N = 6$ 时两种可能的连接方式。
图 2：$N = 6$ 时两种可能的连接方式
编写一个程序，对于给定的 $N$，计算满足上述要求的连接方法的总数模 $1,000,000,000$ 的余数。
输入格式
输入只有一行，包含一个正整数 $N$（$N \le 1,000,000,000$）。
输出格式
输出只有一行，包含连接点阵中点的可行方法数模 $1,000,000,000$ 的余数。
样例
输入样例 1
3
输出样例 1
8
输入样例 2
4
输出样例 2
40
子任务
- $30\%$ 的测试数据满足 $N \le 200$。
- $70\%$ 的测试数据满足 $N \le 100,000$。