Đế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