语言学家 Joseph Greenberg 提出了一种通过大规模比较来确定语言间遗传相关性的方法。在这种方法中，$N$ 种语言被归类为一个或多个语系。形式化地，给定一个包含 $N$ 种不同语言的集合 $\mathcal{L} = \{L_1, \dots, L_N\}$，一个关系分析是一组语系 $\mathcal{F}$，满足以下性质：

• $\mathcal{F} = \{F_1, \dots, F_k\}$，其中 $k$ 为某个正整数
• 对于 $1 \le i \le k$，$F_i \subseteq \mathcal{L}$ 且 $F_i \neq \varnothing$
• 对于 $1 \le i, j \le k$ 且 $i \neq j$，$F_i \cap F_j = \varnothing$
• $\cup_{1 \le i \le k} F_i = \mathcal{L}$

Greenberg 想知道对于 $N$ 种语言，有多少种不同的关系分析。如果两个关系分析 $\mathcal{F}_1$ 和 $\mathcal{F}_2$ 满足 $\mathcal{F}_1 \neq \mathcal{F}_2$，则它们是不同的。你能帮他计算这个数字吗？

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来的 $T$ 行中，每行包含一个整数 $N$ ($1 \le N \le 100$)。

输出格式

对于每个测试用例，输出一行，包含查询的 $N$ 对应的答案，对 $(10^9 + 7)$ 取模。

样例

样例输入 1

4
1
2
3
40

样例输出 1

1
2
5
840750853