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
garmel: 2015-11-29 13:22:03

@marcipanko, because the result is bigger than 1000007....in addition, because the formula contains N*(N+...)

Last edit: 2015-11-29 13:22:36
marcipanko: 2015-11-12 22:25:42

I don't understand why is N%1 000 007 important if N < 1 000 007 so N%1 000 007 = N.
Explanation please?

dk619: 2015-10-26 12:37:17

Don't Forget MOD 1000007.

nithesh2108: 2015-09-25 19:28:38

2 WAs because i forgot to mod by 1000007 :'(

gullu_mishra: 2015-09-13 23:03:14

easy one :) simple maths....silly mistake gave me 1 WA :-p

amous_19291: 2015-08-28 12:20:25

easy question...but a silly mistake caused me 6 wrong answer

shikhar: 2015-08-25 18:38:59

My 30th
3 lines code in python ...loved it

prakash_reddy: 2015-08-09 11:14:57

25th one... in spoj! :)

Medo: 2015-08-08 01:07:00

Doable with BigIntegers...

kvsk: 2015-08-01 07:19:48

Thanks Tony T for clarifying the question. Got WA for taking number of cards needed to make (n mod 1000007) levels instead of taking (number of cards needed to make n levels) mod 1000007.

Last edit: 2015-08-01 07:20:08

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