TopCoder

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

50.0% (10/20)

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10