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
shashank:
20130702 19:49:44
Shortest code ever written on spoj 

alaa hantash:
20130602 20:07:27
i got TLE !! 

hiddenman:
20130131 17:37:53
shortest code ever.......:) 

Abhishek Mittal:
20130109 17:35:35
there is no '\n' in the input test cases as it appears.... 

VARUN KUMARE:
20130102 22:32:22
Last edit: 20130105 21:14:59 

gourav:
20130101 08:43:01
century with this question :) 
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 