Number Man is one of the world’s most powerful superheroes, thanks to his superhuman mathematical powers. With a single thought he can forecast market movements, factor large numbers, extrapolate object trajectories, compute discrete logarithms, estimate probabilities of catastrophic events, and even calculate his tax rate. His favorite hobbies are knitting and high-frequency trading.
But despite his amazing powers, Number Man is very frustrated right now. His ultra-accurate weather prediction formula started giving ultra-inaccurate results, and he spent the last few hours searching for the cause. Did he really make a mistake? He never makes mistakes! And why does everyone else keep giggling? His teammates probably pranked him and made a tiny change on the blackboard while he was distracted. But what symbol did they change? There are so many options.
First, let’s recursively define what is a valid expression:
Ais a valid expression, then
(A)is a valid expression.
Bare valid expressions, then
A*Bare valid expressions.
Number Man has a valid expression E. Every valid expression that has the exact same length as E and differs from E in exactly one character is a potentially correct expression. Note that E itself is not a potentially correct expression.
To calculate the weather value of a valid expression, calculate the expression’s value normally (standard precedence rules apply) and then find the nonnegative remainder that value gives modulo 109 + 7. E.g. the weather value of “
0-2*1” is 109 + 5.
Find the weather value of every potentially correct expression. How many different numbers did you get?
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line and consists of a single line containing the incorrect but valid expression E.
In the easy subproblem I1, the length of each expression is at most 10 000.
In the hard subproblem I2, the length of each expression is at most 1 000 000.
For each test case, print a single number: the number of distinct weather values among all potentially correct expressions.
2 0+0 5*6*7