409876: GYM103821 H FAT Sequences

We call a set $$$S$$$ of $$$K$$$ distinct integers FAT if every integer in the set is greater than or equal to the size of the set. In other words, we call a set of $$$K$$$ integers FAT if for each element $$$s \in S; s \ge K$$$.

For example, sets $$$S_1 = \{3,4,5\}$$$,$$$S_2 = \{1\}$$$ are FAT, but set $$$S_3 = \{1,2,3\}$$$ is not FAT.

Your task is to count the number of FAT sets such that all integers in the sets are not greater than $$$N$$$.

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^5$$$). Description of the test cases follows.

Each of the following $$$T$$$ lines, contains a single integer $$$N$$$ ($$$1\le{N}\le{10}^5$$$).

For each test case, output a single integer denoting the answer for the $$$i_{th}$$$ test case, since the answer could be very large, please print the remainder of dividing it by $$$1\,000\,000\,007$$$.

3
1
2
3

1
2
4

In the first example the only possible set is $$$S = \{1\}$$$.

In the second example the possible sets are $$$S_1 = \{1\}$$$ and $$$S_2 = \{2\}$$$.

In the third example the possible sets are $$$S_1 = \{1\}$$$, $$$S_2 = \{2\}$$$, $$$S_3 = \{3\}$$$ and $$$S_4 = \{2,3\}$$$.