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 1^st Card is 1, 2^nd 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 i^th 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 T (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