One of your friends was in relationship with multiple people at once and it didn’t end very well. Thus he/she chose the path of righteousness and decided to stay in only one relationship or stay single. But not only that, he/she became a motivational speaker and formed an organization to help people to walk through this path.

N people joined his/her organization. He/She takes one person and he/she either pairs that person up with another person in a relationship or keeps that person single. Let’s assume that every person can be paired up with every other person. In how many ways he/she can do that?

Input

First line of input will be T (1<= T <= 100000), denoting the number of test cases.

Next T lines will contain one integer N (1<= N <= 100000) per line.

Output

For each test case print correct answer describe in the description. As, output can be large. Print it modulo 1000000007.

Example

Input:
2
3
100000
Output:
4
823421181

Explanation

For case one, let’s assume they are numbered 1 2 and 3.

Formation can be:

{1} {2} {3} // every person is single

{1} {2, 3} // one is single and two other is in a relationship

{1, 2} {3} // one is single and two other is in a relationship

{1, 3} {2} // one is single and two other is in a relationship

Thus answer is 4.