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
suraj : 2015-01-25 00:47:42

whats wrong with the input ? it always give wa

Md Majid Jahangir: 2015-01-24 18:47:13

can any1 once again specify properly the output and the input format?

Raj Kumar Chauhan: 2015-01-15 07:26:26

WA why?
someone give more tricky tc

Shrikant: 2014-12-21 08:54:25

@kartikay singh
sum=sum%1000007

kartikay singh: 2014-12-12 07:55:44

can any one tell me what this modulo 100007 means????

eightnoteight: 2014-12-08 13:04:49

discrete mathematics - recurrence relations

and take care about the 1000007, costed me 2WA

rahul gautam: 2014-12-05 20:30:02

@Abhishek Deora
mine is giving 70

Mitch Schwartz: 2014-11-07 15:29:42

Spurious newlines in the example I/O is pretty common on SPOJ, it can happen when a problem setter doesn't know HTML and doesn't care enough to investigate.

Last edit: 2014-11-07 15:30:33
CHANDAN KUMAR: 2014-11-07 15:22:20

Taking int in place of long long cost me two WA easy one only you have to watch carefully the pattern and analysise it once

nrl 7: 2014-11-07 14:40:15

First got TLE, now after changing logic got NZEC in Java. Does anyone have any idea why is this so?

Wow! There are no spaces in the test cases input. Although the given input section has spaces, and in some other problem similar spaces were not mentioned in the problem statment, but the test cases had them :\

--ans(Francky)--> Description updated ; thanks for your catch.
As pointed by Mitch, it was a bad HTML format in description.

Last edit: 2014-11-07 16:18:38

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