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