TopCoder

Cheng0928
NLOJ 管理員,題目若有誤請至 Discord 私訊我!

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

你有兩種積木,一種是寬和高皆為 $1$ 的積木,另一種是寬為 $1$,高為 $2$ 的積木 (積木皆不可旋轉)。
現在 Cheng 想要用這些積木填滿寬度為 $2$,高度為 $h$ 的高牆。
Cheng 不希望這個高牆能找到一個高度大於 $0$ 的位置,積木的接縫都在這個高度,這樣他可以直接把這座高牆拆掉。
問有幾種擺放方法?
答案可能很大,請將答案對 $10$$9$ $+7$ 取餘數後輸出。

Input Format

輸入一個正整數 $h$。

Output Format

輸出一個數字代表答案。

Sample Input 1

2

Sample Output 1

3

Sample Input 2

1

Sample Output 2

1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1