An ordered set is a set such that the order in which the objects appear in the set is significant.

For example, ($1,\ 2,\ 3$) and ($2,\ 3,\ 1$) are two different ordered sets of integers.

An ordered set $S$ of integers is said to be a special set if for every element $X$ of the set, the set does not contain the element $X+1$. 

You are given an integer $N$. Determine the number of special sets whose largest element is not greater than $N$. Since, the number of special sets can be very large, print the answer modulo $1000000007$.

For example, if $N = 3$, then there are $5$ special sets that are ($1$), ($2$), ($3$), ($1, 3$), ($3, 1$).

Input format

A single Integer $N$

Output format

A single integer representing the number of special sets that satisfy the provided conditions.

Constraints

$1 \leq N \leq 2000$