Editorial

Let $f(n)$ represent the number of different ways that all $n$ people can join the dance. For example,

• $f(1)=1$, one person dances by himself;

• $f(2)=2$, for two people, there are two options: either dance separately or as a pair;

Consider the $n$-th person:

• If he dances alone, the remaining $n-1$ people can join the dance in $f(n-1)$ ways

• The $n$-th person can choose any of the $n-1$ people as a partner. The remaining $n-2$ people can join the dance in $f(n-2)$ ways.

Thus we have the relation:

Example

Let there be $n=3$ people. They can join the dance in $4$ ways:

• if the third person dances separately: $\{1,2,3\},\{\{1,2\},3\}$;

• if the third person dances in a pair: $\{1,\{2,3\}\},\{2,\{1,3\}\}$.

Compute $f(3)$ using a formula:

Algorithm realization

Declare a modulo constant and an array to store the answers: $dp[n]=f(n)$.

#define MOD 1000000007
long long dp[100001];

Read the input value of $n$.

scanf("%d", &n);

Compute the values sequentially for $f(1),f(2),...,f(n)$, storing each result in the $dp$ array.

dp[1] = 1; dp[2] = 2;
for (i = 3; i <= n; i++)
  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD;

Print the answer.

printf("%lld\n", dp[n]);

Python realization

Declare the modulo constant $MOD$, which will be used for the calculations.

MOD = 1000000007

Read the input value of $n$.

n = int(input())

Declare a list for storing the results, where $dp[n]=f(n)$.

dp = [0] * (n + 1)

Compute the values sequentially for $f(1),f(2),...,f(n)$, storing each result in the $dp$ array.

dp[1] = 1
if n > 1: dp[2] = 2
for i in range(3, n + 1):
  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD

Print the answer.

print(dp[n])