407922: GYM102942 E Password

You are given a string which is the hint of a password. Given string only consist of character '1' to '9' and '-'.

You can replace '-' by any digit from '1' to '9'.

Find the number of ways to make a password by replacing all '-' characters to some digit, such that the digits of the password are in non-decreasing order.

If it is impossible to make the digits of the string in non-decreasing order, print "0" otherwise since the answer can be very large, print the answer modulo $$$10^{9} + 7$$$.

The sequence a is called non-decreasing if $$$a_1 \leq a_2\leq\dots\leq a_n$$$ holds, where $$$n$$$ is the length of the sequence.

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^{2})$$$ $$$-$$$ the number of test cases in the input.

Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ $$$( 1 \leq n \leq 10^{5} )$$$.

The second line of the test case contains a string $$$s$$$ of $$$n$$$ characters, consisting only '1' to '9' and '-'.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases in the input does not exceed $$$10^{5}$$$.

For each test case, If it is impossible to make the digits of the string in non-decreasing order, print "0" otherwise print the number of ways modulo $$$10^{9} + 7$$$

5
5
1---2
3
3-4
7
2--43-4
8
1---23-4
1
-

4
2
0
8
9

In the first test, we have four ways to fill '-' characters $$$111$$$, $$$112$$$, $$$122$$$, $$$222$$$.

In the second test, we have two ways to fill the '-' character, $$$3$$$ or $$$4$$$.

In the third test, it is impossible to convert this into a valid string.