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 \leq n \leq 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