Sum of Prefix‐Suffix Counts over Balanced Parentheses

There are two sets of bracket sequences. Qianhe has n bracket sequences \(S_1,S_2,\dots,S_n\) and Xiaohei has m bracket sequences \(T_1,T_2,\dots,T_m\). For any bracket sequence \(A\) (a string made up of characters '(' and ')'), define

[ f(A)=#{(i,j): 1\le i\le n,;1\le j\le m, ;S_i \text{ is a prefix of }A \text{ and } T_j \text{ is a suffix of }A}]

A balanced (or legal) bracket sequence is a sequence in which the number of opening brackets equals the number of closing brackets and in every prefix the number of '(' is not less than the number of ')'.

Your task is: Given an even integer k, compute the sum

[ \sum_{{\substack{A\text{ is balanced}\|A|=k}}} f(A) ]

modulo (10^9+7).

The input includes the integer k and the lists of sequences \(S_i\) and \(T_j\). Note that a sequence \(S_i\) can only be a prefix of \(A\) if \(|S_i| \le |A|\) and similarly, \(T_j\) can only be a suffix of \(A\) if \(|T_j| \le |A|\). Also note that the sequences \(S_i\) and \(T_j\) themselves may not be balanced.

Input Format: The first line contains three integers n, m and k (with k even). The next n lines each contain a bracket sequence \(S_i\). The following m lines each contain a bracket sequence \(T_j\).

Output Format: Output a single integer, the answer modulo \(10^9+7\).

Note on the solution approach:
A common strategy is to switch the order of summation:

[ \sum_{A} f(A) = \sum_{A}\sum_{i,j}[S_i \text{ is prefix and } T_j \text{ is suffix of } A] = \sum_{i=1}^n \sum_{j=1}^m F(S_i,T_j), ]

where (F(P,Q)) is the number of balanced sequences (A) of length k having P as prefix and Q as suffix. These sequences can be uniquely determined (or counted) by considering the middle part which, together with the fixed prefix and suffix, must form a valid bracket sequence. There are two cases:

• Non‐overlap case: When \(|P|+|Q| \le k\). Let the middle part have length \(L = k - (|P|+|Q|)\). If we denote by \(\Delta(P)\) the net bracket difference (\(#('(')-#(')')\)) and \(m_P\) the minimum prefix sum achieved when scanning \(P\), then a necessary condition is that \(m_P \ge 0\). Similarly, for \(Q\) (which will be appended at the end) one needs \(-\Delta(Q)+m_Q \ge 0\) so that when added to the state from the prefix the whole sequence never becomes negative. Then one counts the number of ways to complete the middle part from the state \(\Delta(P)\) to \(-\Delta(Q)\) in \(L\) steps with steps +1 (for '(') and -1 (for ')') such that the state never drops below 0.
• Overlap case: When \(|P|+|Q| > k\). In this case the prefix and suffix overlap. Let \(o = |P|+|Q|-k\) be the length of the overlap. Then the last \(o\) characters of P must equal the first \(o\) characters of Q. The entire sequence \(A\) is uniquely determined as \(P\) concatenated with \(Q[o:]\). One then simply checks whether this resulting sequence \(A\) is balanced.

Finally, the answer is the sum, over all pairs (i, j), of the number of balanced sequences \(A\) of length k having \(S_i\) as prefix and \(T_j\) as suffix, computed modulo \(10^9+7\).

inputFormat

The first line contains three integers n, m, and k (k is even). The next n lines each contain a non‐empty bracket sequence \(S_i\). The following m lines each contain a non‐empty bracket sequence \(T_j\).

Constraints:
\(1 \le n, m \le 100\) (for example) and k is such that the DP can be computed efficiently.

outputFormat

Output a single integer, the sum over balanced bracket sequences \(A\) of length k of f(A) (where f(A) is the number of pairs \((i,j)\) such that \(S_i\) is a prefix and \(T_j\) is a suffix of \(A\)), modulo \(10^9+7\).

sample

1 1 2
(
)

1