Partial Observation of a Table Tennis Match

Menji loves watching table tennis matches. Unfortunately, due to a huge crowd, he can only hear partial information. A match is composed of a single set played in several rounds. The set is played as follows:

• Two players start with scores \(s_A = 0\) and \(s_B = 0\).
• In each round \(i (\,1 \le i \le n)\), one of the two players wins the round. If player A wins, then \(s_A\) increases by 1; if player B wins, then \(s_B\) increases by 1.
• The set ends immediately once one player reaches at least 11 points and leads by at least 2, i.e. when \(\max(s_A,s_B) \ge 11\) and \(\left|s_A-s_B\right| \ge 2\). Note that if the condition is met in a round, the set stops and no further rounds occur.

For each set, Menji hears that exactly \(n\) rounds have been played. Furthermore, he hears partial score information at some rounds. For every round \(i\), he is given two integers \(a_i\) and \(b_i\). If \(a_i = b_i = -1\) then no score information is available for that round. Otherwise, it is guaranteed that \(0 \le a_i,b_i \le n\) and the score at the end of round \(i\) is either \(s_A = a_i, s_B = b_i\) or \(s_A = b_i, s_B = a_i\>.

Your task is to count the number of winning sequences \(win_1 win_2 \cdots win_n\) (each \(win_i\) is either A or B) that are consistent with all the information Menji heard. Note that the set must end exactly at round \(n\) (i.e. the winning condition is reached at round \(n\) and was not reached in any round before \(n\)).

Since the answer may be large, output it modulo \(998244353\).

Input/Output Specifications: See details below.

inputFormat

The input consists of three lines:

1. An integer \(n\) \( (1 \le n \le \text{appropriate limit})\), the total number of rounds played in the set.
2. \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\). For rounds where no information is heard, the value is \(-1\); otherwise, \(0 \le a_i \le n\).
3. \(n\) space‐separated integers \(b_1, b_2, \dots, b_n\). For rounds where no information is heard, the value is \(-1\); otherwise, \(0 \le b_i \le n\).

It is guaranteed that when \(a_i \neq -1\) (and thus \(b_i \neq -1\)), the score after round \(i\) is either \((s_A, s_B) = (a_i, b_i)\) or \((s_A, s_B) = (b_i, a_i)\).

outputFormat

Output a single integer: the number of valid winning sequences consistent with the partial information, modulo \(998244353\).

sample

1
-1
-1

0