TopCoder

Thumb 100
西瓜
いつか、私を助けてね

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

80.0% (4/5)

Description

「○○一李○○」你筆試的國際會議廳桌上貼著。
「○○一李○○」你上機的電腦螢幕上貼著。
「洞洞么李洞洞!」你身旁的同學如是說。




silentworld陳圓圓 正妹OAO?
一尾✮冀祜 ☂維達(?)樓上李圓圓欸OAO
小可魚渣silentworld: 推正妹
苷-ρ推正魚

身為一隻蚯蚓,你的責任之一就是不斷的鑽洞。不過今天,你要鑽的洞與眾不同,不是在地上鑽,而是山洞,Cave。

在你生存的世界當中,所有的山都長得像一大塊6×n的格子板,這個平板上的每一個格子都可以鑽洞。
在你鑽了洞之後,小可魚會負責在某些洞塞進寶物,然後你每次可以詢問小可魚,
在你目前的洞的哪些方向有寶物。你希望用最好的策略,使得在最壞情況下的詢問次數最少。

前提是你要把洞鑽好!

山洞既然長成的6×n格子板,當然有很神奇的限制。最重要的是,如果一個山洞位在(i,j)的格子點,
那位於(i±1,j±2)、(i±2,j±1)的格子一定不能有山洞,否則因為結構不穩,山洞會崩塌!
此外,為了有足夠多的山洞可以放寶藏,你決定在每一行上都要戳兩個洞。
也就是說,總共要鑽出2×n個山洞來。

那你究竟有幾種鑽法呢?你決定求出鑽法數的末四位數。

Input Format

輸入的第一行只有一個正整數n。

Output Format

輸出只有一行,即鑽法數的末四位數

Sample Input

2

Sample Output

69

Hints

佔總分50%的測資中,1≤n<200
對於所有的測資,1≤n<263

Problem Source

原TIOJ1705 / 建國中學99年校內培訓contest #6 prob 3
problem setter:suhorng

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536
7 2000 65536 65536
8 2000 65536 65536
9 2000 65536 65536