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
Vaporeon: 2015-03-08 21:30:22

AC in first try! 0.00 sec.. do the maths.. ;)

Dushyant Singh: 2015-03-04 17:06:33

@K Bala Vignesh - Wait! :-D

Bala Vignesh [Inactive]: 2015-03-03 16:36:41

why such an easy one for 0.02 points?

Last edit: 2015-03-03 17:45:40
Additya: 2015-02-19 18:29:31

50th <3

Dushyant Singh: 2015-01-28 15:00:20

Take long long int in place of int. I got one WA because of that. Easy problem. Try this after solving above problem: http://www.spoj.com/problems/TRICOUNT/

scyther: 2015-01-27 10:40:18

do remember to mod!!

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


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