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
wille_25:
20210108 09:31:46
Maricruz reminds me of Prison Break series XD


harshh3010:
20201006 15:48:27
Simple maths... just observe the pattern... use long long in C++ and don't forget to take the modulo at the end


manxmaniac:
20200823 15:18:54
don't forget modulo, cost me 1 wa 

ckanzz:
20200813 09:25:38
Easy Pattern can be done in O(1) , Use long long using normal int costed me 2 WA's 

kishor_e:
20200804 13:20:11
find the pattern and figure out the general formula 

malcolm_123ssj:
20200510 15:44:03
Careful. Its not modulo 10^9 + 7 xD


tiksna:
20200111 20:32:59
It's just simple math. Try finding an equation by analyzing the pattern 

hellb0y_suru:
20191220 16:45:54
at i'th level, there are 'i' triangles , each triangle takes 3 cards (except the last level's triangle which takes only 2 cards)


lx_lovin:
20191206 13:53:07
Use Memoization 

dartes:
20191202 01:52:13
Why should we use long long for n? The range is 1 <= n <= 1000000. Costed me few WA's 
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 