Mr. Ronaldo, Jadeja's best friend wants to visit the Jadeja's Restaurant. So Sir wants to make sure that he serves him his favourite dish.

Fortunately Sir Jadeja knows that Mr. Ronaldo likes Indian dishes. So Sir wants to select his best Indian cook. But he's not sure whom to select. So he decides to examine them. Sir told the cook's that 'n' rounds will be conducted in the test and a minimum mark in each round is required to pass the test and he needs to clear all the rounds. Each cook will take part in every round. When Sir returned home, he told Jags (his daughter) about the plan and since her daughter is good at maths, he asked her to tell in how many ways the cooks can fail. Considering yourself as Jags solver Sir Jadeja’s problem.

"Jags always gives right answers".

Input

The first line consist of a integer 'T', denoting the number of test cases. The next t lines each consists of a single integer n.

1 <= n <= 2000000000
1 <= T <= 5000

Output

Output Jags's answer. Since the answer can be quite large, give the answer modulo 1000000007.

Example

Input:
2
1
2

Output:
1
3