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
shashank: 2013-07-02 19:49:44

Shortest code ever written on spoj

alaa hantash: 2013-06-02 20:07:27

i got TLE !!

hiddenman: 2013-01-31 17:37:53

shortest code ever.......:)

Abhishek Mittal: 2013-01-09 17:35:35

there is no '\n' in the input test cases as it appears....

VARUN KUMARE: 2013-01-02 22:32:22

Last edit: 2013-01-05 21:14:59
gourav: 2013-01-01 08:43:01

century with this question :-)


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