830 . 西洋棋排列問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

77.8% (7/9)

Tags

apcsc apcsc-dp

Description

西洋棋有六種棋子：國王、皇后、城堡、騎士、主教與兵。現在在每種棋子都有無限個的情況下，你想要將 $N$ 個棋子排成一列，使得裡面國王與皇后的數量都是偶數，其他棋子則沒有限制。請問有多少種排法？由於方法數可能很多，請輸出答案除以 $10^ 9 + 7$ 後的餘數。

Input Format

輸入只有一行，上面有一個正整數 $N$，代表要將多少個棋子排成一列。

  • $1 \leq N \leq 10^ {18}$

Output Format

輸出一行一個整數，代表符合條件的方法數除以 $10^ 9 + 7$ 後的餘數。

Sample Input 1

3

Sample Output 1

88

Sample Input 2

56562

Sample Output 2

778562666

Hints

Problem Source

2020 北市賽 pC

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~21 $N \leq 10^ 6$ 52
3 0~31 無額外限制 48

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 2 3
12 1000 524288 65536 2 3
13 1000 524288 65536 2 3
14 1000 524288 65536 2 3
15 1000 524288 65536 2 3
16 1000 524288 65536 2 3
17 1000 524288 65536 2 3
18 1000 524288 65536 2 3
19 1000 524288 65536 2 3
20 1000 524288 65536 2 3
21 1000 524288 65536 2 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3
30 1000 524288 65536 3
31 1000 524288 65536 3
Submit
Back to Top