Mike and Mobile Problem Statement

Mike, a little boy who loves solving math problems, was playing with his mom's mobile phone. The mobile keypad includes 12 buttons: 10 digit buttons (0-9) and 2 non-digit buttons ('*' and '#'). Mike wants to find out how many unique numbers he can generate by pressing exactly 'N' buttons. He follows these rules:

1. Mike only presses the digit buttons, ignoring '*' and '#'.
2. After pressing a button, he can either press the same button or a button adjacent to it next.
3. Initially, he can press any of the digit buttons.

Calculate the number of possible numbers modulo 10^9 + 7.

Input:

The input consists of multiple test cases:

• The first line contains a single integer 'T', representing the number of test cases.
• Each test case consists of a single positive integer N, denoting the number of button presses.

Output:

For every test case, print the number of distinct numbers achievable by pressing exactly N buttons. Output each result on a new line.

Example:

Input:

2
1
2

Output:

10
36

Explanation:

For N=1, he can press any of the 10 digits, resulting in 10 numbers.
For N=2, starting from any digit, he can either repeat the digit or move to an adjacent one, yielding more combinations.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 5 * 10^4

Note:

The function should be implemented to solve the problem; printing is handled automatically.