题目描述

考虑一个有 $3×N$ 点的规则网格，网格中的每个点最多有八个相邻点。

我们有兴趣计算连接网格点以形成满足以下条件的多边形的不同方式的数量：

1. 多边形的顶点集由所有 $3×N$ 个点组成。
2. 多边形的相邻顶点是网格中的相邻点。
3. 每个多边形都很简单，即不能有任何自相交。

当 $N=6$ 时的两个可能的多边形如下图。

请编写一个程序，为给定的 $N$ 计算连接点的可能方法数，答案对 $10^9$ 取模。

输入格式

唯一的一行包含一个正整数 $N$。

输出格式

唯一的一行包含一个整数，为对 $10^9$ 取模的连接这些点的方法数。

3

8

4

40

数据范围

对于 $30\%$ 的数据，$0 < N \le 200$。

对于 $70\%$ 的数据，$0 < N \le 10^5$。

对于 $100\%$ 的数据，$0 < N \le 10^9$。