CRDS - Cards

no tags 

Maricruz have a lot of cards, she always uses her cards to build pyramids as shown in the following image:

Cards

A pyramid card of 3 levels. She always wonder how many cards does she need to make a pyramid card of N levels. Your task is to answer that question.

Input

The first line of the input contains an integer 1 <= T <= 1,000. Each of the following T lines will have an integer 1 <= N <= 1,000,000.

Output

For each case, output a single line consisting of the number of cards needed to build a pyramid card of level N modulo 1,000,007.

Example

Input Example
2
3
7

Output Example
15
77

hide comments
aj_254: 2019-05-06 09:47:48

one wa because of forgetting modulo.....btw cakewalk problem just see patern ... diagnally is 2+4+6 and flat is 1 + 2+..n-1
sum it and print modulo .

hritwik: 2019-03-30 10:49:06

take no of cards and also levels as long long int, got 2 WA coz of that.

Itachi_Uchiha: 2019-03-28 15:10:24

PLEASE OUTPUT A NEWLINE AFTER EACH ANSWER!! COSTED ME 2 WAs!!!

subhamiiit: 2019-02-10 11:44:57

one of the easiest!!

satish18: 2019-02-08 10:26:07

for output s%1000007

anant6025: 2019-02-06 22:50:23

Figure out the formula for nth level and from there it is just modulo properties!

Try at least for 1/2 to 1 hr before you jump on to the solution.

phoenix0o0: 2018-12-26 19:06:56

It is not sum(n%1000007) it is sum(n)%1000007.
Got 2 WAs coz of this.

adipat: 2018-10-13 09:34:28

Need to use long long for C/C++ otherwise when calculating the number of cards there will be an overflow.

rohitjain00: 2018-10-12 16:41:47

Use input as long in java, using int got me two Wrong Answers

Yauhen: 2018-09-21 14:08:54

weird modulo.


Added by:Paulo Costa
Date:2012-01-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UGTO