D. Dueling Digits
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the land of Numeria, two friends, Alice and Bob, are fascinated by numbers. Recently, they discovered a curious property about certain pairs of numbers and decided to explore it further. They are interested in finding pairs of numbers with the following properties:

  1. Both numbers have $$$N$$$ digits.
  2. The sum of the digits of Alice's number is equal to the sum of the digits of Bob's number.
  3. For any digit position $$$i$$$, the $$$i$$$-th digit of Alice's number is different from the $$$i$$$-th digit of Bob's number.
  4. Both numbers cannot start with the digit zero.

You have $$$Q$$$ queries, and for each query, you need to determine how many pairs of numbers exist that satisfy these conditions for a given number length $$$N$$$.

Input

The first line contains an integer $$$Q$$$ $$$(1 \leq Q \leq 800)$$$, the number of queries.

Each of the next $$$Q$$$ lines contains a single integer $$$N$$$ $$$(1 \leq N \leq 800)$$$, representing the length of the numbers.

Output

For each query, print a single integer representing the number of valid pairs of numbers that satisfy the conditions for the given length $$$N$$$, because this number can be very large print it modulo $$$10^9 + 7$$$.

Examples
Input
1
2
Output
480
Input
2
3
4
Output
30612
2437704