TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

100.0% (31/31)

Submission's AC Ratio

95.1% (39/41)

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

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