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
madhur4127: 2017-09-25 07:49:52

3 liner in python3!

shubham0028: 2017-09-14 20:17:50

in my case it is showing wrong answer but in ideone its giving the correct output
why????

Last edit: 2017-09-14 20:18:13
mssr_code: 2017-09-06 00:12:34

for c/c++ use long long for "n","answer" for sure

prasanth292130: 2017-09-05 15:54:55

AC in a go................

nitisha1: 2017-09-05 05:57:57

AC in 1 go...................

kholan: 2017-08-28 02:30:52

@vishal3410 be careful to initiallize your variables on the stack properly with c based languages especially N and T in your case, no need to treat two separate cases here
@all easy once you derive the correct formula

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, http://ideone.com/V5SYAy

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


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