Một xâu được gọi xâu tam phân nếu xâu đó chỉ tồn tại các kí tự ~0,1,2~. Hãy đếm số lượng xâu tam phân độ dài ~n~ mà không có ~2~ kí tự ~1~ liền kề nhau.

Dữ liệu

• Dòng đầu là một số nguyên ~n~ ~(1≤ n ≤10^5)~.

Kết quả

• In ra một dòng là số lượng xâu thoả mãn. Kết quả có thể lớn, hãy đưa ra kết quả theo phần dư của ~10^9 +7~.

Ví dụ

Sample Input 1

2

Sample Output 1

8

Sample Input 2

10

Sample Output 2

24960

Giải thích

Trong ví dụ thứ nhất có 8 xâu: ~00, 01, 02, 10, 12, 20, 21, 22~

Nguồn: Beginner Free Contest 30