## CIRCLEDIV - Euler Puzzle

Given some set of points on a circle, you connect every pair of them with a line, find the maximum number of sections do these lines cut the circle into?

### Input

First line for each testcase file contains T denoting the no. of test queries followed by T numbers N, denoting the no. of point on a circle.

### Constraints:

1<= T <= 100000 (105)

1<= N <= 100000 (105)

Note: Use fast I/O methods.

### Output

For each test query, ouput the result in given format. As the result can be large answer the result modulus 1000000007 (109 +7).

Case <test_query_i>: <max_section_circle_cuts_into>

### Example

```Input:
3126
Output:
Case 1: 1Case 2: 2Case 3: 31 ```

hide comments sanchit_aga: 2019-01-07 13:59:37 Good question. Learnt a new formula. pranjulpal18: 2019-01-03 16:15:01 Take help of https://en.m.wikipedia.org/wiki/Dividing_a_circle_into_areas But in this formula n^3 may be greater than 1000000007 and (n^3 % 1000000007)/24 may be not equal to (n^3 / 24)%1000000007 i_love_priya: 2018-11-11 23:12:04 The answer should be the modulus of 10^9+7 . Be careful This **** cost me 20 minutes

 Added by: ad Date: 2018-10-08 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: 3b1b