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
yahya: 2012-02-09 06:54:10

how could it gives Time limit exceed !
it is O(n) ?!!!

Nnavneetsinha: 2012-02-08 04:15:29

do take modulo 1000007 at last .this costed me 3 wa's.

Unicamp Alfa: 2012-02-08 00:02:11

The picture is equivalent to this one: http://cf.ltkcdn.net/boardgames/images/std/50408-283x424-Card_pyramid.jpg
Thanks man.

Last edit: 2012-02-15 11:37:51
Ikhaduri: 2012-02-07 17:03:08

where's the picture?? please upload it, i can't understand the question well.

saibharath: 2012-02-07 16:05:17

i cant see the image using google chrome


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