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
yahya:
20120209 06:54:10
how could it gives Time limit exceed !


Nnavneetsinha:
20120208 04:15:29
do take modulo 1000007 at last .this costed me 3 wa's. 

Unicamp Alfa:
20120208 00:02:11
The picture is equivalent to this one: http://cf.ltkcdn.net/boardgames/images/std/50408283x424Card_pyramid.jpg


Ikhaduri:
20120207 17:03:08
where's the picture?? please upload it, i can't understand the question well. 

saibharath:
20120207 16:05:17
i cant see the image using google chrome 
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 