Adapted from a problem of unknown origin.

There is an array $a$ of $n$ non-negative integers in a computer, where the element at index $i$ ($0 \leq i < n$) has a value in the range $[0, R_i]$.

Due to certain special reasons, the computer will crash if specific combinations of bits appear at the same binary position across these $n$ numbers.

Specifically, let $b_x = \sum_{i=0}^{n-1} \left( \left\lfloor \frac{a_i}{2^x} \right\rfloor \bmod 2 \right) \cdot 2^i$. The computer will not crash if and only if $\forall x \geq 0, b_x \in S$.

Find the number of ways to choose the values of the array such that the computer remains safe. Output the answer modulo 998244353.

Input

The first line contains a positive integer $n$. The next line contains $n$ non-negative integers representing $R_{0 \sim n-1}$.

The last line contains a binary string $s$ of length $2^n$ describing the set of non-negative integers $S$, where the $i$-th character being '1' indicates that $i-1 \in S$ (using 0-based indexing for the string, so the $j$-th character corresponds to the integer $j$).

Output

Output a single integer representing the answer modulo 998244353.

Examples

Input 1

2
4 5
1110

Output 1

19

Input 2

3
7 4 5
11100101

Output 2

80

Subtasks

For all test cases, it is guaranteed that $1 \leq n \leq 18$, $0 \leq R_i < 2^{60}$, and $s_0$ is '1'.