【MX-S5-T4】魔法少女们

原题链接：<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$ | $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$ | $5\times10^5$ | $2\times10^5$ | 无 | | $12\sim13$ | $5\times10^4$ | $10^5$ | $5\times10^5$ | $2\times10^5$ | A | | $14\sim15$ | $5\times10^4$ | $10^5$ | $5\times10^5$ | $2\times10^5$ | B | | $16\sim17$ | $10^5$ | $2\times10^3$ | $10^6$ | $2\times10^5$ | C | | $18\sim19$ | $10^5$ | $10^5$ | $10^6$ | $2\times10^5$ | C | | $20\sim21$ | $10^5$ | $10^5$ | $10^6$ | $2\times10^5$ | 无 | | $22\sim23$ | $2\times10^5$ | $5\times 10^5$ | $10^7$ | $10^6$ | C | | $24\sim25$ | $2\times10^5$ | $5\times 10^5$ | $10^7$ | $10^6$ | 无 | * 特殊性质 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$。