Cho một số nguyên dương n bạn hãy đếm số xâu nhị phân có độ dài n mà không chứa xâu con "111"

Input

Một số tự nhiên duy nhất $n(1\le n\le {10}^6)$

Output

Số xâu nhị phân có độ dài n mà không chứa 101, kết quả có thể rất lớn bạn chỉ cần in ra phần dư của nó chia cho ${10}^9+7$

Ví dụ

Input

4

Output

13

Giải thích Có 13 xâu không chứa xâu con 111 là

0000
0001
0010
0011
0100
0101
0110
1000
1001
1010
1011
1100
1101