题目背景

原题链接：https://oier.team/problems/92。

---

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

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

字符串下标均从 $1$ 开始。

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

$S_i$ 表示字符串 $S$ 的第 $i$ 个字符。

记字符串 $S$ 为 $T$ 的前缀，当且仅当：

• $|S|\leq |T|$，
• $\forall i\in[1,|S|]$，$S_i=T_i$。

记字符串 $S$ 为 $T$ 的后缀，当且仅当：

• $|S|\leq |T|$，
• $\forall i\in[1,|S|]$，$S_{|S|-i+1}=T_{|T|-i+1}$。

合法括号序列的定义如下：

• 空串是合法括号序列。
• 若 $A$ 为合法括号序列，则 $(A)$ 为合法括号序列。
• 若 $A,B$ 为合法括号序列，则 $AB$ 为合法括号序列。

题目描述

千和有 $n$ 个括号序列，分别是 $S_1,S_2,S_3,\dots,S_n$。

小黑有 $m$ 个括号序列，分别是 $T_1,T_2,T_3,\dots,T_m$。

对一个括号序列 $A$，$f(A)$ 为满足以下条件的正整数对 $(i,j)$ 对数：

• $i\in[1,n]$，$j\in [1,m]$；
• $S_i$ 是 $A$ 的前缀且 $T_j$ 是 $A$ 的后缀。

她们想知道对于所有长度为偶数 $k$ 的合法括号序列 $S$，$f(S)$ 的和。答案对 $10^9+7$ 取模。

输入格式

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

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

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

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

输出格式

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

0
1 2 6
(
()
())

4

提示

【样例解释 #1】

长度为 $6$ 的合法括号序列有 ()()()、()(())、(())()、(()())、((()))，分别记作 $S_1,S_2,S_3,S_4,S_5$，答案为 $f(S_1)+f(S_2)+f(S_3)+f(S_4)+f(S_5)=1+1+1+1+0=4$。

【样例 #2】

见附件中的 bracket/bracket2.in 与 bracket/bracket2.ans。

该组样例满足测试点 $1\sim 2$ 的约束条件。

【样例 #3】

见附件中的 bracket/bracket3.in 与 bracket/bracket3.ans。

该组样例满足测试点 $3\sim 4$ 的约束条件。

【样例 #4】

见附件中的 bracket/bracket4.in 与 bracket/bracket4.ans。

该组样例满足测试点 $14\sim 15$ 的约束条件。

【样例 #5】

见附件中的 bracket/bracket5.in 与 bracket/bracket5.ans。

该组样例满足测试点 $20\sim 21$ 的约束条件。

【数据范围】

对于所有测试数据，保证 $1\leq n,m\leq 2\times 10^5$，$1\leq \vert S_i\vert,\vert T_j\vert\leq \min(k,5\times 10^5)$，$1\leq \sum \vert S_i\vert,\sum \vert T_j\vert\leq 10^7$，$2\leq k\leq 10^6$，$k$ 为偶数。

测试点编号	$n,m\leq$	$\vert S_i\vert,\vert T_j\vert\leq$	$\sum \vert S_i\vert,\sum \vert T_j\vert\leq$	$k\leq$	特殊性质
$1\sim2$	$10$		$100$	$15$	无
$3\sim4$	$50$	$100$	$5\times10^3$	$100$
$5\sim8$	$250$	$5\times10^3$	$5\times10^5$	$5\times10^3$
$9\sim11$	$5\times 10^3$	$10^5$		$2\times10^5$
$12\sim13$	$5\times10^4$				A
$14\sim15$					B
$16\sim17$	$10^5$	$2\times10^3$	$10^6$		C
$18\sim19$		$10^5$
$20\sim21$					无
$22\sim23$	$2\times10^5$	$5\times 10^5$	$10^7$	$10^6$	C
$24\sim25$					无

• 特殊性质 A：$k<\min\vert S_i\vert+\min\vert T_j\vert$；
• 特殊性质 B：保证 $S_i,T_j$ 是合法的括号序列；
• 特殊性质 C：$k\geq\max\vert S_i\vert+\max\vert T_j\vert$。