Counting non-decreasing digit sequences

Time limit1sMemory limit128 MB

Summary

Count length-N non-decreasing sequences of digits 0 to 9, modulo 1000000007, for each test case.

Level: Easy3 of 10
Topics: Combinatorics, Number theory
Solved: No attempts yet

Problem

Yasser is an Egyptian coach, and he is running a training camp in Jordan. On the last day the participants solved every hard problem he had brought, so he gave them one more task.

Count the sequences $(d_1, d_2, \ldots, d_N)$ of $N$ digits, each one between 0 and 9, that satisfy $d_1 \le d_2 \le \cdots \le d_N$ . A sequence whose first digit is 0 counts as well.

Input

The first line contains the number of test cases $T$ . ( $T \le 100$ )

Each of the next $T$ lines contains one integer $N$ . ( $1 \le N \le 100000$ )

Output

For each test case, print the number of valid sequences modulo $1000000007$ on its own line.

Examples1

Example 1
Input
```
3
2
3
4
```
Expected output
```
55
220
715
```