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 are in a relationship.
• {1, 2} {3} - one is single and two are in a relationship
• {1, 3} {2} - one is single and two are in a relationship.

Thus the answer is 4.