时间限制： 2.5 秒

空间限制： 1024 MB

题目描述

一个序列被称为“双序列”，当且仅当这个序列具有 $\{x_1,x_2,\cdots,x_k,x_1,x_2,\cdots,x_k\}~(k\ge 1)$ 的形式。例如 $\{2,2,2,2\},~\{1,1\},~\{7,9,9,7,9,9\}$ 都是双序列，而 $\{1\},~\{4,2\},~\{3,3,3\}$ 就不是。

给出长度为 $n$ 的序列 $\{a_1,a_2,\cdots,a_n\}$，其中所有元素都是 $[1,n]$ 之内的正整数。

矩阵 $\mathbf{M}$ 是一个连接关系矩阵（Bridging Relation Matrix，$\mathbf{BRM}$），这是一个 $n\times n$ 的 01 矩阵，注意矩阵的下标是从 1 开始，即左上角第一个元素是 $\mathbf{M}_{1,1}$。

接下来我们基于此定义 $\text{BRM}$ 的子序列。一般地，长度为 $m$ 子序列可以用 $\{a_{p_1},\cdots,a_{p_m}\}~(m\ge 1,1\le p_1<p_2<\cdots < p_m\le n)$ 表示，我们称该子序列对 $\mathbf{M}$ 满足 $\text{BRM}$ 条件当且仅当：$\mathbf{M}_{a_{p_{i}},a_{p_{i+1}}}=1$ 对于任意的 $1\le i\le m-1$ 都成立。

自然地，在对 $\mathbf{M}$ 满足 $\text{BRM}$ 条件的子序列中，也有一部分是双序列。也就是说，我们需要寻找的子序列还要满足以下性质：

• 子序列的长度 $m\equiv 0\pmod 2$；
• $a_{p_i}=a_{p_{i+m/2}}$ 对于任意 $1\le i\le m/2$ 成立。

试计算满足条件的子序列（满足 $\text{BRM}$ 条件的双序列）数量，输出答案对 $10^9+7$ 取模的结果。

输入格式

从标准输入读入数据。

第一行输入一个整数 $n$，表示数列长度。

接下来一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示数列，用空格分隔。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串，只可能为 0 或者 1，第 $i$ 行的第 $j$ 个字符表示 $\mathbf{M}_{i,j}$。

输出格式

输出到标准输出。

输出一个整数，为满足条件的子序列数量对 $10^9+7$ 取模的结果。

2
1 1
01
11

0

样例 1 解释

由于 $\mathbf{M}_{1,1}=0$，子序列中唯一的双序列不满足 $\text{BRM}$ 条件，因此答案为 $0$。

4
1 2 1 2
1111
1111
1111
1111

3

样例 2 解释

满足条件的子序列分别为 $\{a_1,a_3\},~\{a_2,a_4\},~\{a_1,a_2,a_3,a_4\}$。

7
1 2 1 2 2 6 6
0110111
0111011
1111111
1111111
1111111
0000010
1101011

4

样例 3 解释

满足条件的子序列分别为 $\{a_2,a_4\},~\{a_4,a_5\},~\{a_2,a_5\},~\{a_6,a_7\}$。

子任务

对于所有数据，保证 $2\le n\le 500,~1\le a_i\le n$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

特殊性质：$\mathbf{M}_{i,j}=1$ 对所有 $1\le i,j\le n$ 成立。