Animal Cracker Monday

On Animal Cracker Monday (ACM for short), you are given a number of animal crackers, n. Each animal cracker is labeled with a number ranging from 1 to n. You must eat at least one animal cracker, but you cannot eat any two animal crackers that share a digit in their numeric representation. How many different ways can some set of animal crackers be eaten such that the number associated with any two animal crackers does not have any individual digits in common?

For example, if n = $12$, there are $14$ animal crackers marked $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $11$, and $12$ respectively. Crackers $3$, $5$, and $9$ are allowed to be eaten together. Animal crackers $2$, $7$, $8$, and $11$ can also be eaten together. However, crackers $2$, $7$, and $12$ cannot be eaten together because crackers $2$ and $12$ have the digit $2$ in common.

Note: the ordering of animal crackers in each set is inconsequential. Therefore, eating animal crackers $(7, 8, 9)$ is the same as eating animal crackers $(9, 8, 7)$.

The first input line is a number $N$ ($0 \leq N \leq 20$) which corresponds to the number of test cases. Each of the following N lines is a single test case, containing an integer $I$ ($1 \leq I \leq 10^9$). So, if N = $11$, there are $11$ lines following the first line, each with a single test case $I$.

For each test case, output the test case number associated with that test case and follow it with the number of sets of animal crackers modulo $1000000007$.

Sample Input 1 | Sample Output 1 |
---|---|

4 7 8 9 10 |
Case 1: 127 Case 2: 255 Case 3: 511 Case 4: 767 |

Sample Input 2 | Sample Output 2 |
---|---|

3 679 5019 2609 |
Case 1: 158286063 Case 2: 640658343 Case 3: 397337905 |

Sample Input 3 | Sample Output 3 |
---|---|

4 174 956 4072 8993 |
Case 1: 4911233 Case 2: 561134599 Case 3: 283097892 Case 4: 201022736 |