Submit

Status

Discussion / Solution

Ranklist

Back to Problems List

Description

西洋棋中有六種棋子

國王、皇后、主教、騎士、城堡、兵

現在你每種棋子都有無限多顆

你想要從這當中取出 $n$ 顆棋子排成一列

而且你希望讓取出的國王跟皇后數量都為偶數

請問有多少種符合要求的排列方式，並將答案模 $10^{8} + 7$ 輸出

(只要有一個位置放的棋子不同，就視為兩種相異的排列方式)

Input Format

$n$

Input Limits:

$1 \leq n \leq 10^{9}$

Output Format

一個非負整數表示答案 $mod 10^{8} + 7$

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Hints

Subtasks

No.	Testdata Range	Score

TopCoder

Repkironca

🐣🐤🐥

User's AC Ratio

80.0% (4/5)

Tags

High DP 北市賽

Problem Source

2020 台北市資訊學科能力競賽

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Memory Limit (RSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	250000	250000	65536
1	1000	250000	250000	65536
2	1000	250000	250000	65536
3	1000	250000	250000	65536
4	1000	250000	250000	65536
5	1000	250000	250000	65536
6	1000	250000	250000	65536

Submit