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
shyam vinay: 2014-05-13 05:00:50

Note, there's an extra blank line after reading in T value. It costed me 2 WAs.

SHIVAM DIXIT: 2014-04-29 08:35:40

http://cf.ltkcdn.net/boardgames/images/std/50408-283x424-Card_pyramid.jpg
try forming a relation between cards at nth level to that of (n-1)th level...

sarelfeniel: 2014-01-23 08:34:57

Here is the image from KP on a previous page.

http://cf.ltkcdn.net/boardgames/images/std/50408-283x424-Card_pyramid.jpg


Ankit Jain: 2014-01-14 17:12:17

very easy.....:)

xx_xx: 2014-01-14 08:27:22

after 2 times get TLE. nice problem.. :)

Manit Gupta: 2013-12-24 11:17:03

shortest code ever. ;)

Last edit: 2013-12-24 11:17:15
Ruchir Sharma: 2013-11-11 18:54:49

I am not able to see the image.. Where is the image ?

ওয়াসী (Wasi): 2013-11-18 17:24:42

28B in AWK :P

Mostafa 36a2: 2013-10-19 19:09:11

Why all these spoliers Here !!!
please delete theses spoiler comments .

kk: 2013-09-16 17:24:49

i'm getting TLE ...any 1 help


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