## #1568 SegmentDisplay

69  1 s   128 MB

## Description

You have a digital display with an infinite number of positions. Each position consists of 7 segments - 4 vertical and 3 horizontal. Lighting certain segments within a position allows you to represent different decimal digits on the display:

You can use the display to represent different non-negative integers. To represent an integer you need to show its digits, in order, on consecutive display positions. The integers you represent on the display cannot have extra leading zeros.

## Input

The first line of the input gives a number of test cases, T (1 <= T <= 500).

Each case is consists of an integer n. n will be between 0 and 500000, inclusive.

## Output

For each test case, calculate the count each integer that can be represented by lighting exactly n segments. Print this count modulo 1,000,000,007.

### Sample Output

5
2
1
6
10
0
1
0
7
59
0