不知道大家還記不記得,小明被他媽媽要求要收拾好房間,也就是把東西都收進箱子內,
而箱子的大小是 $2 \times n$,物品的大小為 $1 \times 2$,在收納時,可以任意的將物品做旋轉之後再放入,但是物品跟物品不能重疊。
而小明遲遲無法將箱子放滿(也就是有多餘的空間沒被使用到),因此媽媽來檢查的時候又再次的對著小明破口大罵道:「明明有 $x$ 種方法可以把箱子放滿,為什麼你連 $1$ 種都做不到?」
為了不要讓媽媽在罵人的時候講錯數字而自打嘴巴,請你幫媽媽算一下 $x$ 應該是多少。
下圖是 $n = 6$ 的其中一種方式,不同顏色的區塊代表不同的物品。
因為答案可能很大,因此請將 $x$ 與 $1,000,000,007$ 取餘數後再告訴媽媽。
輸入只有一個整數 $n$。
請輸出一個整數 $x$,代表放滿箱子的方法數與 $1,000,000,007$ 取餘數後的結果。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~13 | 無特別限制 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
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 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 |