rt，$2\times10^5$ 真的艹不过去了救救孩子吧 /ll/ll/ll

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 2e5 + 10;
const int MAXM = 5e5 + 10;
const int mod = 1e9 + 7;

int __cnt;

inline void add(int &x, int y) { x += y, x < mod || (x -= mod); }
inline void sub(int &x, int y) { x -= y, x < 0 && (x += mod); }

inline 
int qpow(int b, int p) {
	int res = 1;
	for (; p; p >>= 1, b = (ll)b * b % mod) if (p & 1) res = (ll)res * b % mod;
	return res;
}

int fac[MAXM << 1], ifac[MAXM << 1]; ull p[MAXM];

inline 
void init(int n) {
	*fac = 1;
	for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n; i; i--) ifac[i - 1] = (ll)ifac[i] * i % mod;
}

inline 
int c(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

inline 
int calc(int sx, int sy, int tx, int ty) {
	if (sx > tx || sy > ty) return 0;
	return c(tx - sx + ty - sy, tx - sx);
}

int n, m, k, ans; string tmp;

vector<string> s[MAXM], t[MAXM];

vector<int> ls, lt, dt[MAXM]; vector<vector<int>> ds[MAXM];

vector<vector<ull>> hs[MAXM], ht[MAXM];

map<pair<int, int>, int> cs, ct;

vector<pair<pair<int, int>, int>> vcs, vct;

int main() {
	scanf("%*d%d%d%d", &n, &m, &k), init(k);
	*p = 1;
	for (int i = 1; i <= 5e5; i++) p[i] = p[i - 1] * 131;
	for (int i = 1; i <= n; i++) {
		cin >> tmp; int l = tmp.length(), c = 0, f = 1;
		for (int j = 0; j < l; j++) if ((tmp[j] == '(' ? c++ : c--) < 0) { f = 0; break; }
		if (!f) continue; int x = 0, y = 0;
		for (int j = 0; j < l; j++) tmp[j] == '(' ? x++ : y++;
		if (x > k || y > k) continue; cs[make_pair(x, y)]++;
		s[l].emplace_back(tmp), ls.emplace_back(l);
		ds[l].emplace_back(vector<int>(l)), c = 0;
		for (int j = 0; j < l; j++) ds[l].back()[j] = (tmp[j] == '(' ? c++ : c--);
		hs[l].emplace_back(vector<ull>(l)), hs[l].back()[0] = tmp[0];
		for (int j = 1; j < l; j++) hs[l].back()[j] = hs[l].back()[j - 1] * 131 + tmp[j];
	}
	sort(ls.begin(), ls.end()), ls.erase(unique(ls.begin(), ls.end()), ls.end());
	for (int i = 1; i <= m; i++) {
		cin >> tmp; int l = tmp.length(), c = 0, f = 1;
		for (int j = l - 1; ~j; j--) if ((tmp[j] == ')' ? c++ : c--) < 0) { f = 0; break; }
		if (!f) continue; int x = k / 2, y = k / 2;
		for (int j = 0; j < l; j++) tmp[j] == '(' ? x-- : y--;
		if (x < 0 || y < 0) continue; ct[make_pair(x, y)]++;
		t[l].emplace_back(tmp), lt.emplace_back(l), dt[l].emplace_back(c);
		ht[l].emplace_back(vector<ull>(l)), ht[l].back()[0] = tmp[0];
		for (int j = 1; j < l; j++) ht[l].back()[j] = ht[l].back()[j - 1] * 131 + tmp[j];
	}
	sort(lt.begin(), lt.end()), lt.erase(unique(lt.begin(), lt.end()), lt.end());
	for (int x : ls) {
		for (int y : lt) {
			if (x + y <= k) continue;
			int l = x + y - k; unordered_map<ull, int> cnt;
			for (int i = 0; i < s[x].size(); i++) {
				ull val = hs[x][i][x - 1];
				if (l < x) val -= hs[x][i][x - l - 1] * p[l];
				cnt[val * 114514191981llu + ds[x][i][x - l]]++;
			}
			for (int i = 0; i < t[y].size(); i++) {
				ull val = ht[y][i][l - 1];
				ans += cnt[val * 114514191981llu + dt[y][i]];
			}
		}
	}
	for (pair<pair<int, int>, int> x : cs) vcs.emplace_back(x);
	for (pair<pair<int, int>, int> x : ct) vct.emplace_back(x);
	for (pair<pair<int, int>, int> x : vcs) {
		for (pair<pair<int, int>, int> y : vct) {
			int sx = x.first.first, sy = x.first.second;
			int tx = y.first.first, ty = y.first.second;
			if (sx > tx || sy > ty) continue;
			int res = calc(sx, sy, tx, ty);
			sub(res, calc(sx, sy, ty - 1, tx + 1));
			add(ans, (ll)x.second * y.second % mod * res % mod);
		}
	}
	printf("%d", ans);
}