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
nikhil03: 2016-08-30 20:02:43

Taking n as long int will give unexpectedly give you WA!!! Use long long..
AC in sec time!!!

epsilonalpha: 2016-08-15 15:03:45

First I thought that the modulo is the general 10^9+7 so that costed me two WA, and then three WA for choosing int. Stupid me.

rachsbodla: 2016-07-27 19:02:31

very easy problem.AC in one go :)

baadshah_: 2016-06-22 17:32:53

AC in one go (Simple AP)
take long long int and finally %1000007

vineetpratik: 2016-06-12 13:13:26

took N as int got WA took long long int. AC!

sonali9696: 2016-05-31 10:29:44

the output line means print ans modulo 1,000,007, "N modulo 1,000,007" makes no sense. Cost me 1 WA :/

vaibhavk31: 2016-05-27 15:41:10

use long long int in place of of int
costed me 3 WA

vinu0103: 2016-05-08 12:40:56

thanks tony t

abhilc: 2016-04-24 08:45:18

Arithmetic Progression :)

adi_tdkr: 2016-04-02 09:55:05

What is the meaning of this lines:
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.


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