改编自某一道不明来源的题。

计算机内有一个长度为 $n$ 的非负整数数组 $a$ ，下标为 $i(0 \leq i < n)$ 的元素取值范围为 $\left[0, R_i\right]$ 。

由于某些特殊原因，若这 $n$ 个数的同一个二进制位上的取值出现某些组合则计算机会炸掉。

具体地，设 $b_x=\sum_{i=0}^{n-1}\left(\left\lfloor\frac{a_i}{2^x}\right\rfloor \bmod 2\right) \cdot 2^i$ ，那么只有当 $\forall x \geq 0, b_x \in S$ 时计算机不会炸。

求能保证机子安全的数组取值的方案数，答案对 998244353 取模。

输入格式

第一行一个正整数 $n$ ，接下来一行 $n$ 个非负整数表示 $R_{0 \sim n-1}$ 。

最后一行包含一个长度为 $2^n$ 的 01 字符串 $s$ 描述非负整数集合 $S$ ，第 $i$ 个字符为 1 表示 $i-1 \in S$ 。

输出格式

输出一行一个整数，表示答案对 $998244353$ 取模的结果。

样例数据

样例 1 输入

2
4 5
1110

样例 1 输出

19

样例 2 输入

3
7 4 5
11100101

样例 2 输出

80

子任务

对于所有的数据，保证 $1≤n≤18,0 ≤ Ri < 2^{60}$，且 $s_0$ 为 $1$。