你有兩種積木,一種是寬和高皆為 $1$ 的積木,另一種是寬為 $1$,高為 $2$ 的積木 (積木皆不可旋轉)。
現在 Cheng 想要用這些積木填滿寬度為 $2$,高度為 $h$ 的高牆。
Cheng 不希望這個高牆能找到一個高度大於 $0$ 的位置,積木的接縫都在這個高度,這樣他可以直接把這座高牆拆掉。
問有幾種擺放方法?
答案可能很大,請將答案對 $10$$9$ $+7$ 取餘數後輸出。
輸入一個正整數 $h$。
輸出一個數字代表答案。
2
3
1
1
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | 無額外限制 | 100 |