Pair the people

There are $n$ people at a party. Each person can either join the dance as a single individual or as part of a pair with any other person. Find the number of different ways in which all $n$ people can join the dance.

Input

One integer $n(1\le n\le 10^5)$.

Output

Print the number of different ways all $n$ people can join the dance. Print the answer modulo $10^9+7$.

Examples

Let we have $n=3$ people. They can dance in $4$ different ways: $\{1,2,3\},\{\{1,2\},3\},\{1,\{2,3\}\},\{\{1,3\},2\}$.