题目描述

观者遇到一个发光立方体，这个立方体是一个 $n$ 维的 Hypercube。

具体地，我们定义一个 $n$ 维 Hypercube 是一张 $2^n$ 个点的无向图，每个点编号为一个长为 $n$ 的 01 串，两个点 $u,v$ 之间有连边当且仅当 $u,v$ 的汉明距离为一，定义两个 01 串的汉明距离为不相同的位数。

观者在这个 Hypercube 上画了三个高维球，第 $i$ 个高维球的球心位于 $s_i$，半径为 $r_i$，这个高维球包含了所有满足 $j$ 与 $s_i$ 的 Hamming 距离不超过 $r_i$ 的结点 $j$（容易发现 $j$ 与 $s_i$ 的 Hamming 距离即这两个结点在图上的最短路长度）。

她想知道，这三个球的并集包含多少结点。由于答案过大，你只需回答其对 $10^9+7$ 取模的结果。

输入格式

第一行一个正整数 $n$。

接下来三行，每行一个长为 $n$ 的 01 串 $r_i$ 与一个正整数 $s_i$（$1\leqslant i\leqslant 3$）。

输出格式

一行一个非负整数，表示答案。

4
1 1101
2 0111
1 1001

14

数据范围

对于 $100\%$ 的数据，$2\leqslant n\leqslant 6000,0\leqslant r_i\leqslant n-1$。

特殊性质 A：保证 $s_1=s_2$。

特殊性质 B：保证 $r_1\leqslant 5$。

特殊性质 C：保证 $s_1$ 与 $s_2$ 恰好按位不同。

样例

样例