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\)