Coco 拥有一块 $3 \times N$ 的巧克力和 $1$ 个国际象棋中的王（King），并想玩一个叫做“国王游戏”的游戏。国王游戏（与同名的饮酒游戏无关）的规则是：从巧克力的左上角格子出发，按照国际象棋中王的移动规则，恰好访问巧克力的每个格子一次，最后到达右下角格子即可获胜。王可以从当前格子移动到相邻的 $8$ 个方向的格子，但不能移动到巧克力外面。
Coco 想知道在国王游戏中获胜的方法数。请帮 Coco 解决这个疑问。
第一行包含一个整数 $N$。
第一行输出答案模 $10^9$ 的余数。
2
6
6
11563
$1 \le N \le 10^3$
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: