Gavin has decided to construct a new enclosure for his goats. He has many
several goats, and he wants each one to be separated from each other goat. He
starts by making a large circle in an open field, then hammers N posts into the ground
at various points around the circle. However Gavin doesn't use any measuring equipment,
instead choosing to rely on his own estimations and intuitions, and so as a result the
posts are not evenly distributed. Then, Gavin ties pieces of
rope between each pair of posts, forming R "regions" which are bounded by the
tied-up ropes.
With N=4 posts placed around a circle, a maximum of R=4 regions could be created.
Gavin plans to somehow teach the goats not to step over these ropes, so that each goat will have its own region.
But he begins to wonder... if he places N posts, how many of these regions could he possibly create?
Problem Statement
Given N posts placed around a circle, what is the maximum number of regions R that could be
created by tying ropes between pairs of posts?
Assume you would be allowed to choose the placement of the posts around the circle.
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow, each holding a single value N.
Answer
Should consist of Q space-separated values, corresponding to the number of
regions R in each testcase.
Report all values modulo 1000000007.
Example
input data:
6
2
3
4
5
10
999999999
answer:
0 1 4 11 246 375