yz 是 Z 国的领导人，他规定每个地区的名字只能为 26 个小写拉丁字母的一个。由于地区数有可能超过 26 个，便产生了一个问题，如何辨别名字相同的地区？于是 yz 规定，一个地区的描述必须包含它的所有上级，且上级按次序排列。于是，一个地区的描述是一个字符串。比如说，一个地区的名字为 \tt c，它的上级为 \tt b，\tt b 的上级为 \tt a，\tt a 没有上级，那么这个地区就描述为 \tt abc。显然，这个描述同时包含了 \tt c 的上级 \tt b 和 \tt b 的上级 \tt a 的描述，分别为 \tt ab 和 \tt a。
值得注意的是，每个地区最多有一个上级，同一上级的地区之间名字不同，没有上级的地区之间名字不同。
现在，yz 对外公布了 n 个地区的描述，这些描述中包含了 Z 国所有地区的描述，并让你处理来访者的旅行问题。
现有 m 对人访问这个国家，对于每对人，第一个人喜欢第 i 个描述中的第 j 个地区，设这个地区描述为 s_1，第二个人喜欢第 k 个描述中的第 l 个地区，设这个地区描述为 s_2。他们为了统一行程，决定访问描述为 s 的地区（显然他们只关心地区的名字，并非是地区本身），设 s 的长度为 t，s 需要满足以下条件：
- t\leq j，t\leq l。
- s[1\cdots t]=s_1[j-t+1\cdots j]，s[1\cdots t]=s_2[l-t+1\cdots l]，即 s 为 s_1 中 1 到 j 位与 s_2 中 1 到 l 位的公共后缀。
- t 最大化。
为了不使输出过大，你只需把这个字符串按照如下生成的 26 进制数转成 10 进制后 \bmod\ (10^9+7) 后输出：
- a \to 0；
- b \to 1；
- ……
- z \to 25。
比如地区 \tt cab 被编码成 2\times26^2+0\times26^1+1\times26^0=1353。