改编自某一道不明来源的题。
计算机内有一个长度为 $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$。
| 测试点编号 | 特殊限制 |
|---|---|
| $1 \sim 4$ | $n \le 2$ |
| $5 \sim 7$ | $\forall i, R_i \le 3$ |
| $8 \sim 10$ | $n \le 9$ |
| $11 \sim 13$ | $n \le 11$ |
| $14 \sim 16$ | $n \le 13$ |
| $17 \sim 20$ | 无 |