Description

千和有 $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$ 取模。

Input Format

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

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

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

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

Output Format

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

0
1 2 6
(
()
())

4

Hint

【样例解释 #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$ 为偶数。

• 特殊性质 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$。