Cho một số tự nhiên n.Hỏi có bao nhiêu dãy ~ a_1,a_2,..,a_n ~ sao cho:

• Với mọi ~1\le i \le n~ thì ~ 1\le a_i \le 7 ~.
• Tổng của tất cả các số trong dãy chia hết cho 7.

Lưu ý dãy các dãy số trên phân biệt thứ tự tức là (1,2,3) và (2,3,1) được coi là 2 dãy khác nhau.

Input

Duy nhất 1 số tự nhiên n (~n<10^{18}~).

Output

Vì kết quả có thể rất lớn nên chỉ cần in ra số dư của nó khi chia cho ~10^9+7~.

Sample

Input #1

2

Output #1

7