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}\)
Test Case #1:
There are 3 ways of achieving number: 1122 which is "Analytically Stable". Therefore the answer is 3.
Test Case #2:
There are 3 ways of achieving number: 5566, 1 way of achieving number: 1122, and 1 way of achieving number: 3344. Therefore the answer is 5.
Challenge Name
Dialpad Software Engineer Hiring Challenge
Dialpad Software Engineer Hiring Challenge