Một xâu được gọi là xâu tam phân nếu xâu đó chỉ gồm 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 \le n \le 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.