SLNCRD - Selling Greeting Cards

You are familiar with greeting cards, right?

On the occasion of EID, Mahir along with his cousins, decided to sell special greeting cards for wishing EID. As per decision, they set up their small stall. And they started selling. Initially they have N Eid cards. There is a serial number of each EID card. The serial number of 1st Card is 1, 2nd card is 2 and so on. The serial numbers of the EID Cards are written on it.

Mahir came up with a great pricing idea. As they are looking to make much profit, the price of the EID cards are not fixed. They will fix according to their idea. So let’s describe it.

Firstly, they will consider two things, the serial number of the card they are selling and the number of cards left before selling current card. And the price of this card will be product of this two.

Let’s make it straight forward:

  • Consider, they are selling ith card. So the serial number is i.
  • And so there will be actually n-i+1 cards left before selling this card.
  • So the price of the card will be i * (n-i+1).

It is guaranteed that they will sell all the cards. Your task is to calculate the total income after selling all the cards.

Input

The first line of the input contains an integer (1 ≤ T ≤ 1,000). Each of the following T lines will have an integer N (1 ≤ N ≤ 1,000,000,000) .

Output

For each case, output a single line consisting of the total income of Mahir modulo 1,000,000,007.

Example

Input:

2
5
10

Output:

35
220


Added by:Fuad
Date:2021-01-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2021-06-16 23:31:22
Ahhh, learned the difference between Python / and // operators! Now AC
2021-06-03 18:47:14
Works for example input, but get WA. Cannot figure out why - seems straight forward.
2021-02-13 07:21:08 Amitayush Thakur
Subtle spoiler:
An obvious mathematical simplification hidden beind a verbose story.

Last edit: 2021-02-13 07:21:30
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.