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
hparmar_cs13: 2016-03-13 13:11:07

Easiest problem in SPOJ...AC in one go :-)

Arnabjyoti Kalita: 2016-03-04 06:50:48

Very easy.. just take care of the datatypes :)

Pranay Kumar: 2016-02-04 12:11:33

Too easy!!
Move to tutorials!!!!

ayush sinha: 2016-02-01 22:12:51

useless question

kshitizmiglani: 2016-01-17 09:56:37

2 WA because question is not clear;
remember if f(n) is the real ans, modulo is not f(n%1000007), its f(n)%1000007

damsehgal: 2016-01-04 18:56:37

DP solution is acceptable but why not evaluate the formula.

pvsmpraveen: 2015-12-26 13:44:54

AC , Thinking about the problem and forget Modulus ;) cheers

sarthak_8: 2015-12-19 13:12:32

First attempt got TLE for Brute Force .. changed approach and got 3 WA for not having long long int in place of int. Finally AC. B|

sarthak_8: 2015-12-19 12:49:48

@Satish Brute Force would give you a TLE. Think of a simpler way which does not need to include the for loop. Think of a simpler equation. :)

satish: 2015-12-10 11:25:52

My solution is getting wrong answer.However I am getting correct answer in my IDE and Ideone.
My solution -
http://ideone.com/eZtqyV


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