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
wille_25: 2021-01-08 09:31:46

Maricruz reminds me of Prison Break series XD
AC in one go (0.00s)

harshh3010: 2020-10-06 15:48:27

Simple maths... just observe the pattern... use long long in C++ and don't forget to take the modulo at the end

manxmaniac: 2020-08-23 15:18:54

don't forget modulo, cost me 1 wa

ckanzz: 2020-08-13 09:25:38

Easy Pattern can be done in O(1) , Use long long using normal int costed me 2 WA's

kishor_e: 2020-08-04 13:20:11

find the pattern and figure out the general formula

malcolm_123ssj: 2020-05-10 15:44:03

Careful. Its not modulo 10^9 + 7 xD

tiksna: 2020-01-11 20:32:59

It's just simple math. Try finding an equation by analyzing the pattern

hellb0y_suru: 2019-12-20 16:45:54

at i'th level, there are 'i' triangles , each triangle takes 3 cards (except the last level's triangle which takes only 2 cards)
so the total answer will be = (3*1 + 3*2 + 3*3 + 3+4 ...... 3*n) - (n)
which is equal to , 3*(1+2+3+4+5 ...... + n) - n ;
::: dont forget to use long long instead of int, dont forget to use modulo

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


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