CRDS  Cards
Maricruz have a lot of cards, she always uses her cards to build pyramids as shown in the following image:
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
Shrikant:
20141221 08:54:25
@kartikay singh


kartikay singh:
20141212 07:55:44
can any one tell me what this modulo 100007 means????


eightnoteight:
20141208 13:04:49
discrete mathematics  recurrence relations


rahul gautam:
20141205 20:30:02
@Abhishek Deora


Mitch Schwartz:
20141107 15:29:42
Spurious newlines in the example I/O is pretty common on SPOJ, it can happen when a problem setter doesn't know HTML and doesn't care enough to investigate. Last edit: 20141107 15:30:33 

CHANDAN KUMAR:
20141107 15:22:20
Taking int in place of long long cost me two WA easy one only you have to watch carefully the pattern and analysise it once 

nrl 7:
20141107 14:40:15
First got TLE, now after changing logic got NZEC in Java. Does anyone have any idea why is this so?


karan:
20141012 17:38:35
:D 

Amit Doshi:
20140522 18:17:26
An easy problem which I managed to screw, owing to blank spaces.


Francky:
20140514 14:43:24
Image inserted in description. 
Added by:  Paulo Costa 
Date:  20120130 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  UGTO 