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
raichu7: 2017-08-19 23:48:44

AC in one go :)

vishal3410: 2017-07-15 22:52:56

what's wrong with my code it shows runtime error, <snip>

Last edit: 2022-08-10 16:58:07
vish_14: 2017-06-16 13:43:34

Didn't read the question carefully & got WA because of modulus.
Too much of overconfidence :(

sandeep_4141: 2017-06-15 21:24:05

try to use pen and copy !! it's take less than 5 minute to evaluate problem and drive direct formula !!
easy one !! 1 line code

ramesh_961: 2017-06-03 11:31:44

Nice one! Mat be the reason for using Long Long is for ex: For integers P,Q (P*Q), may result in Long Long and and that result will be Long Long only if P and Q are Long Long! After that applying MOD may yield correct results..
Correct me if i am wrong!!

nilabja16180: 2017-02-15 14:32:01

Not taking long long costed me two WA :(

shivendra_420: 2017-02-07 13:19:33

unable to understand why long int is giving wrong ans.....but long long gives AC although constraints are satisfied by long int

Last edit: 2017-02-07 13:20:20
vengatesh15: 2017-01-19 18:35:47

1 line code... AC in 1 go

soodan: 2016-12-26 14:16:26

hint : learn about triangular numbers and formula for sum of 1+ 2+ 3...n .

soodan: 2016-12-26 14:03:31

bottom up dp


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