C1487 [HEOI2012]旅行问题

yz 是 Z 国的领导人，他规定每个地区的名字只能为 $26$ 个小写拉丁字母的一个。由于地区数有可能超过 $26$ 个，便产生了一个问题，如何辨别名字相同的地区？于是 yz 规定，一个地区的描述必须包含它的所有上级，且上级按次序排列。于是，一个地区的描述是一个字符串。

比如说，一个地区的名字为 $c$，它的上级为 $b$，$b$ 的上级为 $a$，$a$ 没有上级，那么这个地区就描述为 $abc$。显然，这个描述同时包含了 $c$ 的上级 $b$ 和 $b$ 的上级 $a$ 的描述，分别为 $ab$ 和 $a$。

值得注意的是，每个地区最多有一个上级，同一上级的地区之间名字不同，没有上级的地区之间名字不同。现在，yz 对外公布了 $n$ 个地区的描述，这些描述中包含了 Z 国所有地区的描述，并让你处理来访者的旅行问题。现有 $m$ 对人访问这个国家，对于每对人，第一个人喜欢第 $i$ 个描述中的第 $j$ 个地区，设这个地区描述为 $s_1$，第二个人喜欢第 $k$ 个描述中的第 $l$ 个地区，设这个地区描述为 $s_2$。他们为了统一行程，决定访问描述为 $s$ 的地区（显然他们只关心地区的名字，并非是地区本身），设 $s$ 的长度为 $t$，$s$ 需要满足以下条件：

1. $t \le j, t\le l$

2. $s[1..t] = s_1[j-t+1 … j]， s[1..t] = s_2[l-t+1 … l]$；（即 $s$ 为 $s_1$ 中 $1$ 到 $k$ 位，与 $s_2$ 中 $1$ 到 $l$ 位的公共后缀）

3. $t$最大化。为了不使输出过大，你只需把这个字符串按照如下生成的 $26$ 进制数转成 $10$ 进制后 $\bmod 1000000007$ 后输出：

   a->0
   b->1
   ...
   z->25
   

   比如地区 $cab$ 被编码成 $2 \times 26^2 + 0 \times 26^1 + 1 \times 26^0 = 1353$。

样例输入 1

2
aabb babb
2
1 3 2 3
1 4 2 4

样例输出 1

1
1