终于遇到唐诗翻译题了，看 5 分钟没看懂。orz

$n$ 个人，每个人可以与别人配对，或者自己单独一人。与别人配对可以看做合并成了一个人。问：这些人排队一共有多少种方案？（对 $10^9+7$ 取模，$n \le 10^5$）

样例中 $n=3$ 时，有如下 $4$ 种情况：

可爱递推题。

设 $dp_i$ 表示前 $i$ 个人排队的方案数。对于新来的第 $i$ 个人，他可以与前面 $i-1$ 个人其中一个配对，也可以单独一人。分开来看两种情况。

如果他与前面一个人配对，那么和谁呢？有 $i-1$ 种可能。这时前面 $i-2$ 个人的方案数为 $dp_{i-2}$，根据乘法公式有 $dp_{i-2} \times (i-1)$。否则他单独一人，那么只需要统计前 $i-1$ 个人排队的方案数即可，方案数为 $dp_{i-1}$。两者相加即可。