SP31279 AGPC01G - Eat Pray Love

题目描述

一共 \(N\) 个人，他要么单独一个人，要么与其他人配对，若每个人可以与任何人配对，一共有多少种方式？

输入格式

第一行是 \(T\)（\(1 \le T \le 5000\)），表示接下来的行数。

接下来的 \(T\) 行每行包含一个整数 \(N\)（\(1 \le N \le 100000\)）。

输出格式

由于答案可能过大，所以答案对 \(1000000007\) 取模。

输入输出样例 #1

输入 #1

2
3
100000

输出 #1

4
823421181

说明/提示

【样例解释】

对于样例中的第 \(2\) 行，假设他们的编号是 \(1, 2, 3\)。

组合可以是：

\(\{1\} \{2\} \{3\}\) - 每个人都是单身。

\(\{1\} \{2, 3\}\) - 一个人是单身，另外两个人在一起。

\(\{1, 2\} \{3\}\) - 一个人是单身，另外两个人在一起。

\(\{1, 3\} \{2\}\) - 一个人是单身，另外两个人在一起。

因此答案是 \(4\)。