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
```
