题目描述

对于变量的赋值语句，箭头是一种常用的表达方式。

给一个长度为 $n$ 的序列 $a$，定义下面两种箭头语句：

• $a_u\gets v$：把 $a_u$ 赋值为 $v$，语句的值为 $v$。
• $v\to a_u$：把 $a_u$ 赋值为 $v$，语句的值为 $v$。

进而可以定义嵌套的箭头语句，令 $A,B$ 分别是一个语句：

• $A\gets B$：先计算 $B$，并令答案为 $q$。接下来计算 $A$，并令答案为 $a_p$，此时计算 $A$ 带来的副作用不会影响 $q$ 的值。最后执行语句 $a_p\gets q$，整体语句的值就是 $a_p\gets q$ 的值。
• $A\to B$：先计算 $A$，并令答案为 $p$。接下来计算 $B$，并令答案为 $a_q$，此时计算 $B$ 带来的副作用不会影响 $p$ 的值。最后执行语句 $p\to a_q$，整体语句的值就是 $p\to a_q$ 的值。

比如语句 $(a_i\to a_j)\gets(a_k\to a_l)$ 会被解析为依次执行 $a_k\to a_l$，$a_i\to a_j$，$a_j\gets a_l$ 三个语句。

现在给你一个长度为 $n$ 的箭头语句，第 $i$ 个操作数是 $a_i$，你需要给它加括号规定优先级，问最终能得到多少种答案。

具体形式可以参考样例解释。

输入格式

第一行一个个正整数 $n$。

第二行 $n$ 个正整数，表示序列 $a$。

第三行 $n-1$ 个正整数，保证每个数都是 0 或 1。第 $i$ 个正整数若为 0 则表示第 $i$ 个操作数和第 $i+1$ 个操作数之间有一个 $\gets$，否则有一个 $\to$。

输出格式

一行一个正整数，表示最终能得到多少种答案。

样例组 #1

样例组下载：Download。

输入样例 #1

5
1 2 3 2 1
0 1 1 0

输出样例 #1

2

样例解释

原始表达式：$a_1\gets a_2\to a_3\to a_4\gets a_5$

答案只可能是 1 或 2，下面分别给出一种可能的加括号方式：

• $((a_1\gets a_2)\to (a_3\to a_4))\gets a_5=1$。
• $(a_1\gets a_2)\to (a_3\to (a_4\gets a_5))=2$。

样例组 #2

见附加文件中 arrow2.in / arrow2.ans

样例组 #3

见附加文件中 arrow3.in / arrow3.ans

样例组 #4

见附加文件中 arrow4.in / arrow4.ans

样例组 #5

见附加文件中 arrow5.in / arrow5.ans

数据范围

各测试点分数等分。

• 对于测试点 $1\sim5$，保证 $n\le 10$。
• 对于测试点 $6\sim10$，保证所有箭头的方向都一样。
• 对于测试点 $11\sim15$，保证所有相邻的箭头的方向都不一样。
• 对于测试点 $16\sim20$，无特殊限制。

对于全部数据，$2\le n\le5\times10^5$，$1\le a_i\le 10^9$。