You are given with a number $N$.  A 4 digit number is said to be "Analytically Stable", if the four digits of the number are of the form, $\{x,x,x+1,x+1\}$, where $0 \le x \lt 9$. 

Your task is to pick 4 digit subsequences of the given number $N$, such that the 4 digit number formed by them is Analytically Stable. 

Output the number of such sub-sequences. As answer may be too large, output the answer mod $10^9 + 7$.

Input
The first line of input contains an integer $T$, denoting the number of test cases. 
The first line of each test case contains a number $N$.

Output
For each test case output the number of Analytically Stable sub-sequences mod $10^9 + 7$.

Constraints

$1 \le T \le 50\\ 1 \le N \le 10^{30000}$