• 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.

Input

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

Output

• 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ả sau khi chia dư cho ~10^9 + 7~.

Sample

Input #1

2

Output #1

8

Input #2

10

Output #2

24960