How many n digit number satisfy the following condition:
i^{th} digit \equiv i \pmod{3}
Please note that the indexing starts from 1 at the leftmost digit.
For example, 42 satisfies the condition.
### Input
- The first line contains an integer n.
### Output
- Print the number of numbers satisfy the above condition, modulo 10^9+7.
### Constraints
- 1 \le n \le 10^{18}.
### Example
Input:
2
Output:
9
