##### Time limit: 0.05s

##### Memory limit: 64MB

##### Input: kfib.in

##### Output: kfib.out

# Task

Given a natural number $K$, find the $K^{th}$ term of the Fibonacci sequence, modulo $10^9 + 7$.

# Input data

The first line of the file `kfib.in`

contains the natural number $K$.

# Output data

The first line of the file `kfib.out`

will contain the answer to this task.

# Constraints and clarifications

- $1 \leq K \leq 10^{18}$

# Example 1

`kfib.in`

```
6
```

`kfib.out`

```
8
```

## Explanation

The first $10$ terms of the Fibonacci sequence are:

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55$

The $6^{th}$ term is $8$.

# Example 2

`kfib.in`

```
123456789
```

`kfib.out`

```
62791945
```