문제1568--SegmentDisplay

### 1568: SegmentDisplay

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 305  통과: 94
[제출] [채점기록] [묻고답하기]

#### 문제 설명

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.

#### 입력 설명

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.

#### 출력 설명

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.

#### 입력 예시 Copy

5
2
1
6
10
0

#### 출력 예시 Copy

1
0
7
59
0