Đếm số lượng số có $n$ chữ số thỏa mãn điều kiện sau: $\text{Chữ số thứ i}\equiv i\text{ mod 3}$

Chỉ số bắt đầu từ $1$, từ trái sang phải.

Ví dụ, $42$ là một số có $2$ chữ số thỏa mãn.

Input

• Dòng đầu tiên gồm số nguyên $n$

Output

• In ra số lượng số thỏa mãn điều kiện trên, modulo ${10}^9+7$

Điều kiện

• $1\le n\le {10}^{18}$ .

Sample Input 1

2

Sample Output 1

9