#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Dynamic Programming (Fibonacci) - Classic Problems | Repovive

CLS3. Dynamic Programming (Fibonacci)

1s256 MB

The Fibonacci sequence is defined as:

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$

Given $n$ , compute $F_n \mod (10^9 + 7)$ .

Constraints

$0 \le n \le 10^6$

Input

$n$

Output

$F_n \mod (10^9 + 7)$

Samples

Input

Explanation

For this input, the required output is 0.

Output

Input

Explanation

For this input, the required output is 1.

Output

Input

Explanation

For this input, the required output is 55.

Output

Input

Explanation

For this input, the required output is 517691607.

Output

517691607

The Fibonacci sequence is defined as:

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$

Given $n$ , compute $F_n \mod (10^9 + 7)$ .

$0 \le n \le 10^6$

$F_n \mod (10^9 + 7)$