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
navidator: 2018-05-26 01:24:16

Be aware of that mod 1000007.

nightwayne: 2018-05-05 13:00:01

Can anyone help me figure out why it is giving WA when I take N as 'int' but AC when I take it as 'long long int' ? Range of N here is given till 10^6, well under the limit of 'int' ?

satyampnc: 2018-03-25 16:38:09

my 100th :)

nessaa_05: 2018-03-14 14:57:43

module caused me 2 wrong answer.

srjsunny: 2018-01-24 16:20:33

2*(sum of n terms)+(sum of n-1 terms (for base ))

vkash: 2018-01-01 11:02:24

just one line of code,derive formula..AC in 2nd submission cz of i didn't notice modulo...!!!

spandana09: 2017-11-30 17:14:50

don't take modulo while calculating,take it once only at the end and declare the ans and level as long long int .

sandeep_123: 2017-10-20 11:13:49

"modulo 1000007" cost me 2 WA (-_-)

trivedi_jt2021: 2017-10-13 13:18:42

easy question but difficult to understand written language in question.

kush_pathak01: 2017-10-13 13:16:54

wrong explanation there should be comma after N in last line


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