Ciulama 是一种罗马尼亚炖菜。它非常美味，应该趁热食用。它可以用蘑菇、鸡肉制作，较少情况下也会用猪肉。

你妈妈给你做了 ciulama。你极其讨厌 ciulama，所以现在你想找一个好借口来推迟这不可避免的时刻。你记起了高级格点几何算子（Advanced Latticeal Geometric Operators, ALGO）的作业。这足以让你免于这顿饭，但现在你面临着一个更难的问题。

这个问题涉及 $k$ 维空间中的整点。设 $n_1, n_2, n_3, \dots, n_k$ 为正整数。 考虑所有满足在每个维度上都有 $0 \le x_i \le n_i$ 的整点坐标 $(x_1, x_2, x_3, \dots, x_k)$。 每个点都有一个与之关联的二进制值，初始时为 0。

在一次操作中，你选择满足在每个维度上都有 $0 \le y_i \le n_i$ 的 $y_1, y_2, y_3, \dots, y_k$，然后翻转（将 0 变为 1，或将 1 变为 0）所有满足在每个维度上都有 $0 \le x_i \le y_i$ 的点 $(x_1, x_2, x_3, \dots, x_k)$ 的值。

设 $m$ 为所有 $\{n_i\}$ 中的最大值。给你 $m + 1$ 个期望的二进制值 $f(0), f(1), \dots, f(m)$。你的目标是使每个点 $(x_1, x_2, x_3, \dots, x_k)$ 的值达到 $f(x_1) \oplus f(x_2) \oplus \dots \oplus f(x_k)$。求实现这一目标所需的最少操作次数。由于这个数字可能非常大，请将其对 $10^9 + 7$ 取模后输出。

操作 $\oplus$ 表示二进制异或。

输入格式

第一行输入包含两个整数：$k$ 和 $m$（$1 \le k \le 10^5$，$1 \le m \le 10^6$）。

第二行包含 $k$ 个由空格隔开的正整数 $n_1, n_2, n_3, \dots, n_k$（$1 \le n_i \le m$）。值 $m$ 是所有 $n_i$ 中的最大值。

第三行包含一个由 $m + 1$ 个二进制值组成的字符串 $f(0), f(1), \dots, f(m)$。这些值之间没有空格。

输出格式

输出一个整数：实现目标状态所需的最少操作次数对 $10^9 + 7$ 取模后的结果。

样例

输入样例 1

1 5
5
011010

输出样例 1

4

输入样例 2

3 6
4 6 1
0101010

输出样例 2

12

说明

在第一个样例中，你可以进行四次操作：分别选择 $y = 0$，$y = 2$，$y = 3$ 和 $y = 4$。