4460 . 西洋棋
Description
西洋棋中有六種棋子
國王、皇后、主教、騎士、城堡、兵
現在你每種棋子都有無限多顆
你想要從這當中取出 $n$ 顆棋子排成一列
而且你希望讓取出的國王跟皇后數量都為偶數
請問有多少種符合要求的排列方式，並將答案模 $10^8 + 7$ 輸出
(只要有一個位置放的棋子不同，就視為兩種相異的排列方式)
Input Format
$n$
Input Limits:
$1 \leq n \leq 10^9$
Output Format
一個非負整數表示答案 $\text{mod } 10^8 + 7$
Sample Input 1
1
Sample Output 1
4
Sample Input 2
2
Sample Output 2
18
Sample Input 3
1000000
Sample Output 3
7662499
Hints
Subtasks
| No. | Testdata Range | Score |
|---|
