Baltic Olympiad in Informatics: 2015 Day 1, Problem 1

Byteasar is a fan of both bowling and statistics. He has written down the results of a few past bowling games. Unfortunately, some characters in the notes are blurry, and thus unreadable. Byteasar asks you to write a program to calculate the number of distinct games which are consistent with his notes.

A bowling game consists of $n$ frames: $n-1$ simple frames and one final frame. In a typical game $n=10$. At the beginning of each frame $10$ pins are put standing upright at the end of a lane and a player gets no more than two (or three for the final frame) attempts (shots) to throw a bowling ball down the lane to try to knock down as many pins as possible. Each frame is denoted by two (for a simple frame) or three (for the final frame) characters.

For each shot the player receives as basic points the total number of pins knocked down in this shot. The player's basic points in each frame are the sum of basic points of all the shots in this frame. If all $10$ pins are knocked down in a simple frame (and therefore $10$ basic points are earned), the player gets additional bonus points.

For a simple frame the rules are the following:

• If a player knocks down all $10$ pins in the first shot of a frame, she gets a strike and the frame ends. As bonus points she gets the sum of basic points of her next two shots. A strike is denoted as x-.

• If a player knocks down all $10$ pins using both shots of a frame, she gets a spare. As bonus points she gets the basic points of her next shot. A spare is denoted as A/, where $A$ is a digit describing the number of pins knocked down in the first shot of the frame.

• If $9$ or fewer pins are knocked down after both shots, the player gets just basic points and such a frame is denoted as AB, where $A$ is the one-digit number of pins knocked down in the first shot, and $B$ is the one-digit number of pins knocked down in the second shot $(A+B<10)$.

Note that bonus points are included to the score of a frame in which the strike or the spare was obtained, regardless of the fact that the exact number of bonus points depends on future shots in next frames.

For the final frame the rules are the following:

• Initially the player receives two shots in this frame. If $9$ or fewer pins are knocked down in the two shots, the frame ends. Otherwise (if the first two shots are a spare or the first shot is a strike), the player receives a third shot in the frame. Whenever the player knocks down all the pins in any of the three shots, the pins are reset to the initial configuration for the next shot. The score of the final frame is the total number of pins knocked down (note that no bonus points are earned due to strikes and spares).

• Overall there are seven possible configurations of the final frame with the following outcomes ($A$ and $B$ stand for one-digit numbers):

Denotation	Description	Frame Score
xxx	Three consecutive strikes	$30$
xxA	Two consecutive strikes and a shot with $A$ pins knocked down	$20+A$
xA/	A strike and a spare with $A$ pins knocked down on its first shot	$20$
xAB	A strike and two following shots with $A$ and $B$ pins knocked down respectively $(A+B<10)$	$10+A+B$
A/x	A spare with $A$ pins knocked down on the first shot and a strike	$20$
A/B	A spare with $A$ pins knocked down on the first shot and $B$ pins knocked down in the last shot	$10+B$
AB-	Two shots with $A$ and $B$ pins knocked down respectively $(A+B<10)$	$A+B$

Each game is described as a sequence of $2n+1$ characters. At the end of the game the total number of points after each frame may be calculated. For example, for a game of $n=10$ frames described as 08x-7/2/x-x-23441/0/x, the player's points after respective frames were as follows:

Frame	Denotation	Basic Points	Bonus Points	Frame Score	Total
$1$	08	$0+8$	$-$	$8$	$8$
$2$	x-	$10$	$7+3$	$20$	$28$
$3$	7/	$7+3$	$2$	$12$	$40$
$4$	2/	$2+8$	$10$	$20$	$60$
$5$	x-	$10$	$10+2$	$22$	$82$
$6$	x-	$10$	$2+3$	$15$	$97$
$7$	23	$2+3$	$-$	$5$	$102$
$8$	44	$4+4$	$-$	$8$	$110$
$9$	1/	$1+9$	$0$	$10$	$120$
Final	0/x	$0+10+10$	$-$	$20$	$140$

Input Specification

The first line of input contains one integer $q$ $(1\le q\le 25)$, specifying the number of test cases to consider. The following $3q$ lines of input contain descriptions of test cases. Each test case is described by three lines of input.

The first line of a test case description contains one integer $n$ $(2\le n\le 10)$, specifying the number of frames. The second line contains a sequence of $2n+1$ characters which denotes the game description from Byteasar's notes. Blurry characters are replaced by ? characters. The third line contains $n$ integers, the total number of points after each frame, separated by spaces. In each number either all digits are readable, or all digits are blurry. Numbers in which all digits are blurry are replaced by -1.

Output Specification

Your program should output $q$ lines, one line per each test case in the same order as in the input.

For each test case your program should write one integer: the number of possible distinct games corresponding to the test case. Two games are considered different if and only if they differ in at least one shot, that is, their $(2n+1)$-character game descriptions are different. You can assume that there is at least one game consistent with each test case in the input. You can assume that the result fits into 64-bit signed integer type.

Constraints

Subtask	Conditions (in each test case)	Points
1	At most six ? characters in the input sequence.	$16$
2	The result is at most ${10}^9$.	$17$
3	No game whose description contains any characters x or / is consistent with the input data.	$26$
4	The input sequence ends with 00- (that is, the player obtained $0$ points in the last frame) and last $min(3,n)$ frame scores provided in the third line of input data are all -1.	$23$
5	No additional constraints.	$18$

Sample Input

2
10
08x-7/2/x?x-23??1/???
8 -1 40 60 82 97 102 110 120 140
5
x-x-23?/00-
22 37 42 52 52

Sample Output

9
10

Explanation for Sample

In the first case, in frame $5$ after the character x, the only possible character is -. In frame $8$ the player got $8$ points in total. Thus there are $9$ possibilities for how this sum could have been obtained: $0+8,1+7,\dots ,8+0$. There were no bonus points in frame $9$. Therefore, there were no points on the first shot of the final frame. To obtain $20$ points in the last two shots, the only possibility is a spare with a following strike in the last shot of the frame. Therefore there are $9$ different valid games which correspond to this input data.

In the second case, any character from $0$ to $9$ is consistent with the input data.

Additional Sample Test

In the data we provide you with an additional sample test with multiple test cases with $n=2$.