Analytically Stable
Tag(s):

## Algorithms, Dynamic Programming, Dynamic programming, Hash Maps

Problem
Editorial
Analytics

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}$

SAMPLE INPUT
2
1515732322
1351355246246
SAMPLE OUTPUT
3
5
Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

Challenge Name