User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

50.0% (5/10)

Description

不知道大家還記不記得,小明被他媽媽要求要收拾好房間,也就是把東西都收進箱子內,
而箱子的大小是 $2 \times n$,物品的大小為 $1 \times 2$,在收納時,可以任意的將物品做旋轉之後再放入,但是物品跟物品不能重疊。

而小明遲遲無法將箱子放滿(也就是有多餘的空間沒被使用到),因此媽媽來檢查的時候又再次的對著小明破口大罵道:「明明有 $x$ 種方法可以把箱子放滿,為什麼你連 $1$ 種都做不到?」

為了不要讓媽媽在罵人的時候講錯數字而自打嘴巴,請你幫媽媽算一下 $x$ 應該是多少。

下圖是 $n = 6$ 的其中一種方式,不同顏色的區塊代表不同的物品。

因為答案可能很大,因此請將 $x$ 與 $1,000,000,007$ 取餘數後再告訴媽媽。

Input Format

輸入只有一個整數 $n$。

  • $1 \leq n \leq 2 \cdot 10^5$

Output Format

請輸出一個整數 $x$,代表放滿箱子的方法數與 $1,000,000,007$ 取餘數後的結果。

Sample Input 1

2

Sample Output 1

2

Sample Input 2

5

Sample Output 2

8

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~13 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (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
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1