Da Vinci Numbers
All submissions for this problem are available.
A number (integer) N is said to be a Da Vinci number if no two consecutive digits of the number are equal and no four consecutive digits form an incrementing sequence. A sequence of digits is called incrementing if each digit is one more than the previous digit. For example, 1234 is an incrementing digit sequence and 1245 is not (because 4 - 2 = 2).
How many D digit Da Vinci numbers exist?
The first line of input consists of a single integer T the number of test cases. The description of the test cases follow (one test case per line). The description of each test case consists of a single integer D on a line by itself.
For each test case print, on a new line, the answer to the problem modulo 109 + 7.
- 1 ≤ T ≤ 100000
- 1 ≤ D ≤ 100000
2 2 3
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions