[HEOI2012]旅行问题
题号：NC20544
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

第一行给定一个整数n
第2…n+1行:每i+1行给定一个字符串a[i],表示第i个描述。
接下来一行一个整数m
接下来m行:每行给定四个整数i,j,k,l，字母含义与题目描述一致。

输出描述:

共m行，每行一个整数，表示答案字符串的编码。
示例1

输入

复制 
2
aabb babb
2
1 3 2 3
1 4 2 4

输出

复制 
1
1

说明

【样例说明】
询问1中的公共后缀有ab和b，但是没有ab这个地区，只有b地区，所以只能选择b这个 地区；
询问2中的公共后缀有abb、bb和b，但是没有abb和bb这两个地区，只有b地区，所以 只能选择b这个地区。

备注:

设这个国家地区总数数为 tot（注意：输入的字符串总长度可能超过 tot！）
对于 30%的数据，满足；
对于 50%的数据，满足；
对于 80%的数据，满足 ；
对于 100%的数据，满足；
保证输入文件不超过 20MB。