TopCoder

User's AC Ratio

100.0% (71/71)

Submission's AC Ratio

91.6% (87/95)

Description

在假期的某一天,你和你的朋友們決定搭乘飛行船俯瞰美麗的風景。然而,在旅程開始半小時的時候,恐怖份子宣稱他們已將前一天從實驗室裡偷走的超級病毒──肺噬病毒──放在飛行船的某處並使其開始散播。肺噬病毒,顧名思義,就是會將人的肺吞噬殆盡的一種病毒。而在開始散播後,肺噬病毒在第$s-1$分鐘末至第$s$分鐘末所增殖的個數$F_s$稱為「肺噬數列」。肺噬數列有以下性質:
(1) $F_1=1, F_2=2$
(2) $F_{n+2}=F_{n}+F_{n+1}\quad\forall n\in\mathbb{N}$(意思是「對於所有正整數n」。)

可怕的肺噬病毒固然令人緊張,可是比起這個,你更在意從開始散播到現在增殖的病毒總數被3除之後餘數是多少。為了計算,你決定做以下操作:
(1) 如果從病毒開始散播到現在過了$t$分鐘,那麼就留$t$行的空格,其中第$i$行總共留了$F_i$個空格。
(2) 寫完空格後,從上到下、每一行從左到右,依序填入$1,2,0,1,2,0,1,2,0,\cdots$。
(3) 最後一個寫下的數字就是你想要的那個數字。
但是從病毒散播到現在已經過了有點久的時間,所以你想要借助電腦之力完成這件事。而且你希望可以看到整個計算過程。

Input Format

輸入只有一行,包含一個正整數$t\leq 30$,代表病毒散播至今過了幾分鐘。

如果你稍作計算(可能用小算盤或者其他的,不重要),你會發現:
病毒增殖的數量必定會在int範圍內。
(因為很重要所以要粗體標示。)

Output Format

請輸出如題的計算過程。(請參考範例輸出。)

Sample Input

5

Sample Output

1
20
120
12012
01201201

Hints

有沒有發現「費氏數列」和「肺噬數列」其實很不一樣?

Problem Source

Problem set / Description by Paupière
建國中學105學年度校隊選拔:初試pB

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 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10