A sequence $(u)$ is defined as follows:

$u_0=0$

$u_1=1$

$u_n=u_{n-1}+u_{n-2}+1$ for all $n\ge 2$.

Given integer $n$, find the value of $u_n$ modulo ${10}^9+7$.

Input

A single integer $n$.

Note: Use $64$bit integer to input number.

Output

A single integer.

Constraints

Subtask $1$ $(30\mathrm{\%})$: $0\le n\le 20$.

Subtask $2$ $(30\mathrm{\%})$: $0\le n\le {10}^6$.

Subtask $3$ $(40\mathrm{\%})$: $0\le n\le 9\ast {10}^{18}$.

Example

Input:

4

Output:

7