Competitions

# PP1 and Competitive Programming

# Reduce to one

Consider a list of integers **L**. Initially **L** contains the integers **1** through **n**, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in **L** is not important. You should perform the following operation **n** − **1** times:

- Choose two elements of the list, let's denote them by
**x**and**y**. These two elements may be equal. - Erase the chosen elements from
**L**. - Append the number
**x**+**y**+**x*****y**to**L**.

At the end, **L** contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo `10`

+ ^{9}**7**.

#### Input

The first line contains the number of test cases **t**. Each of the next **t** lines contains a single integer **n** (**1** ≤ **n** ≤ `10`

).^{6}

#### Output

For each test case, print a single line containing one integer - the maximum possible value of the final number in the list modulo `10`

+ ^{9}**7**.

Input example #1

3 1 2 4

Output example #1

1 5 119