魔法少女们

【题目背景】

祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

以下是本题所用记号的约定。

字符串下标均从 1 开始。

|S| 表示字符串 S 的长度。

Si 表示字符串 S 的第 i 个字符。

记字符串 S 为 T 的前缀，当且仅当：∣S∣≤∣T∣，|S|]∀i∈[1,∣S∣]，Si=Ti。记字符串 S 为 T 的后缀，当且仅当：∣S∣≤∣T∣，∀i∈[1,∣S∣]，S∣S∣−i+1=T∣T∣−i+1。合法括号序列的定义如下：空串是合法括号序列。若 AA 为合法括号序列，则 (A) 为合法括号序列。若 A,B 为合法括号序列，则 AB 为合法括号

【题目描述】

异客在一个无限循环的 01 字符串 T=S^∞ 上进行着他的旅程，其中 SS 的长度为 n，T 的第 i 个字符为 Ti

异客的视野有限，只能看到后面 m 个字符。

异客会进行 q 次旅程，每次起点不同，移动次数也不同。

当异客在 Ti 上时：若 Ti+1…i+m 中存在 1，则异客下一次会移动到其中最远的一个 1 上。否则，异客下一次会移动到下一个字符 Ti+1 上。你需要告诉异客，他会在哪里停下。由于答案会很大，你只需要告诉他对 10^9+7 取模后的结果。

千和有 n 个括号序列，分别是 S1,S2,S3,…,Sn。

小黑有 m 个括号序列，分别是 T1,T2,T3,…,Tm。

对一个括号序列 A，f(A) 为满足以下条件的正整数对 (i,j) 对数：i∈[1,n]，j∈[1,m]；Si 是 A 的前缀且 Tj 是 A 的后缀。她们想知道对于所有长度为偶数 k 的合法括号序列 S，f(S) 的和。答案对 10^9+7 取模。

【输入格式】

第一行，一个正整数 c，表示测试点编号。特殊地，对样例，c=0。

第二行，三个正整数 n,m,k，其中 k 为偶数。

接下来 n 行，每行一个字符串 Si。

接下来 m 行，每行一个字符串 Tj。

【输出格式】

仅一行，一个自然数，表示答案对 10^9+7 取模后的值。

【样例输入】

0
1 2 6
(
()
())

【样例输出】

4

【样例说明】

长度为 6 的合法括号序列有 ()()()、()(())、(())()、(()())、((()))，分别记作 S1,S2,S3,S4,S5，答案为 f(S1)+f(S2)+f(S3)+f(S4)+f(S5)=1+1+1+1+0=4。

【数据规模与约定】

对于所有测试数据，保证 1≤n,m≤2×10^5，1≤∣Si∣,∣Tj∣≤min(k,5×10^5)，1≤∑∣Si∣,∑∣Tj∣≤10^7，2≤k≤10^6，k 为偶数。

【来源】

在此键入。