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
lx_lovin: 2019-12-06 13:53:07

Use Memoization

dartes: 2019-12-02 01:52:13

Why should we use long long for n? The range is 1 <= n <= 1000000. Costed me few WA's

trhgquan: 2019-11-04 16:28:01

using DP, AC in 1 node.

darker__space: 2019-10-02 15:54:00

make sure you take modulo(% ) at the final answer ...applying modulo meanwhile ...in wrong way may change ur answer and give wrong answer :<

codequant: 2019-09-24 09:59:50

Piece of cake! Just find the pattern in the image given. NOTE: Don't forget the last Modulo part of the problem.

s_h_i_1: 2019-07-27 08:25:54

general formula is very easy to derive... think level wise ... after that use modulo property [ (a*b)%c =( (a%c)*(b%c))%c ]

aryan29: 2019-05-31 23:16:47

Easy one

py_tyagi: 2019-05-11 07:45:54

doing it level%(1000000007) but it is(1000007)

aj_254: 2019-05-06 09:47:48

one wa because of forgetting modulo.....btw cakewalk problem just see patern ... diagnally is 2+4+6 and flat is 1 + 2+..n-1
sum it and print modulo .

hritwik: 2019-03-30 10:49:06

take no of cards and also levels as long long int, got 2 WA coz of that.


Added by:Paulo Costa
Date:2012-01-30
Time limit:0.449s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UGTO