代码：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007; 
int n, m, k;
long long dp[25][35][25][2];
bool g[25][25];
string s;
bool isnum(char c) {
	return '0' <= c && c <= '9';
}
bool isop(char c) {
	return c == '+' || c == '-' || c == '*' || c == '/';
}
long long dfs(int u, int step, int l, bool hz) {
	if (dp[u][step][l][hz] != -1)
		return dp[u][step][l][hz];
	long long ans = 0;
	if (step == k) {
		if (!l && !isop(s[u]))
			return dp[u][step][l][hz] = 1;
		else
			return dp[u][step][l][hz] = 0;
	}
	for (int i = 0; i < n; i++)
		if (g[u][i]) {
			if (isnum(s[i])) {
				if (isnum(s[u]) && !hz)
					ans = (ans + dfs(i, step + 1, l, 0)) % mod;
				else if (isop(s[u]) || s[u] == '(')
					ans = (ans + dfs(i, step + 1, l, s[i] == '0')) % mod;
			} else if (s[i] == '(') {
				if (isop(s[u]) || s[u] == '(')
					ans = (ans + dfs(i, step + 1, l + 1, 0)) % mod;
			} else if (s[i] == ')') {
				if (l > 0 && (isnum(s[u]) || s[u] == ')'))
					ans = (ans + dfs(i, step + 1, l - 1, 0)) % mod;
			} else {
                if(isnum(s[u]))
					ans = (ans + dfs(i, step + 1, l, 0)) % mod;
                if(s[u] == ')' || (s[u] == '(' && s[i] == '-'))
					ans = (ans + dfs(i, step + 1, l, 0)) % mod;
			}
		}
	return dp[u][step][l][hz] = ans % mod;
}
signed main() {
	cin >> n >> m >> k >> s;
	int u, v;
	long long ans = 0;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		--u;
		--v;
		g[u][v] = g[v][u] = 1;
	}
	for (int i = 0; i < n; i++) {
		if (s[i] == '(')
			ans = (ans + dfs(i, 1, 1, 0)) % mod;
		else if (s[i] == '-')
			ans = (ans + dfs(i, 1, 0, 0)) % mod;
		else if (isnum(s[i]))
			ans = (ans + dfs(i, 1, 0, s[i] == '0')) % mod;
	}
	cout << ans;
	return 0;
}

测试点