Server Time:

User's AC Ratio in this contest

61.9% (13/21)

Submission's AC Ratio in this contest

20.0% (13/65)

Description

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

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

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

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

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

Input Format

輸入只有一個整數 $n$,代表箱子的大小為 $2 \times n$。

  • $1 \leq n \leq 10^{18}$

Output Format

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

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~21 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 65536 65536 1
1 500 65536 65536 1
2 500 65536 65536 1
3 500 65536 65536 1
4 500 65536 65536 1
5 500 65536 65536 1
6 500 65536 65536 1
7 500 65536 65536 1
8 500 65536 65536 1
9 500 65536 65536 1
10 500 65536 65536 1
11 500 65536 65536 1
12 500 65536 65536 1
13 500 65536 65536 1
14 500 65536 65536 1
15 500 65536 65536 1
16 500 65536 65536 1
17 500 65536 65536 1
18 500 65536 65536 1
19 500 65536 65536 1
20 500 65536 65536 1
21 500 65536 65536 1