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:
3
1
2
6 Output: Case 1: 1
Case 2: 2
Case 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