# Pair the people

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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≤n≤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}$.

Input #1

Answer #1

Submissions 586

Acceptance rate 21%