Server Time:

User's AC Ratio in this contest

66.7% (16/24)

Submission's AC Ratio in this contest

27.6% (16/58)

Description

這題跟 pB 的差別只在於這題多了大小為 $1 \times 1$ 的物品。

不知道大家還記不記得,小明被他媽媽要求要收拾好房間,也就是把東西都收進箱子內,
而箱子的大小是 $2 \times n$,物品的大小分為 $1 \times 1$ 和 $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

7

Sample Input 2

5

Sample Output 2

228

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~17 無特別限制 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
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1