OR

题号：NC225344
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

There are two sequences of length $n-1$ , $b=(b_2,b_3,\ldots,b_n)$ , $c=(c_2,c_3,\ldots,c_n)$ . Here, each $b_i$ , $c_i$ is a non-negative integer.

Now, the sequence $a=(a_1,a_2,\ldots,a_n)$ considers beautiful if and only if for all $i$ $(2 \leq i \leq n)$ , $b_i = a_{i-1} \, \text{or} \, a_{i}$ , $c_i = a_{i-1} + a_{i}$ and each $a_i$ is a non-negative integer.

Now, Toilet-Ares asks you to calculate the number of beautiful sequences.

输入描述:

The first line contains one integer   - the length of sequence .

The second line contains  integers   - the elements of sequence .

The third line contains  integers   - the elements of sequence .

输出描述:

Print one number - the number of beautiful sequences.

示例1

输入

复制

4
7 5 5
7 9 5

输出

复制