Many computer games implement alchemy skill. It allows the player to create different elixirs using various ingredients. Usually players have to find out recipes for the elixirs they need. Usually they do it by trying to mix some ingredients. Given that there are n different ingredients and any elixir can be made by mixing three or more different ingredients, can you count the maximal number of various elixirs that can be made using alchemy skill.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test consist of a single integer n.

Constraints

1 <= t <= 10000
1 <= n <= 10⁹

Output

For each test print the maximal number of different elixirs that can be made modulo 1000000007.

Example

Input:
4
3
4
100
100000

Output:
1
5
976366234
607673554