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
hugox14: 2015-07-17 03:26:12

Anyone know what structure should be used to solve a type error = runtime error (SIGSEGV) ?

Akshat Mathur: 2015-06-29 22:23:23

Too easy to complete 100 on spoj :-)

Pradd: 2015-06-29 08:04:16

4 lines in Python, around 11 in C++. There is a simple relationship between the number of cards and levels. Create a naive implementation first and study the relation for some aribitary values. You can then implement a simple one liner function to get the number of cards.

r0bo_dart: 2015-06-17 14:55:07

Using recursion here will be a disaster :P

Sidharth Yatish: 2015-06-08 15:16:04

Good problem :) Brute force won't work. Simple maths :)

Aguilar: 2015-05-22 23:07:14

5 WA ToT

Arpan Mukherjee: 2015-05-14 19:43:43

2 WA -_- 1 for not taking modulo and another for taking modulo as 10^9+7 -_- here modulo isn't 10^9+7,cost me a WA :'(

NIKHIL KUMAR SINGH: 2015-04-24 18:27:54

Easy Peasy ... 1 WA due to not taking the modulo

Chisty: 2015-04-23 05:38:27

Do take modulo at last. this costed me 1 wa's. Thanks to @Nnavneetsinha

Tony T.: 2015-04-18 05:32:41

instructions for the output could really be clearer, taught me that we should all remember to explain ourselves better ;-)

for the benefit for the people doing this question, the output requests for (number of cards needed to make n levels) mod 1000007, not number of cards needed to make (n mod 1000007) levels.


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