Find the $n^{th}$ Fibonacci number modulo $10^9+7$.
### Input
- A single line contains an integer $n$.
### Output
- Print the $n^{th}$ Fibonacci number modulo $10^9+7$.
### Constraints
- $ 1 \le n \le 10^{18}$.
### Example
Input:
```
5
```
Output:
```
5
```
