Read problem statements in [Russian], [Bengali], and [Mandarin Chinese] as well.

You are given an undirected graph with $N$ nodes (numbered $1$ through $N$) and $M$ edges. Each edge connects two distinct nodes. However, there may be multiple edges connecting the same pairs of nodes, and they are considered to be distinct edges. A lowercase English letter is written in each node.

You are also given a string $S$ with length $L$. A *beautiful path* is a sequence of $L-1$ edges such that there is a sequence of $L$ nodes with the following properties:
for each valid $i$, the $i$-th edge connects the $i$-th and $(i+1)$-th of these nodes
for each valid $i$, the $i$-th character of $S$ is written in the $i$-th of these nodes

There are no other restrictions — a path may visit nodes or edges any number of times in any order.

Determine the number of beautiful paths in the graph. Since the answer can be very large, compute it modulo $10^{9}+7$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $M$ and $L$.
The second line contains a single string $S$ with length $L$.
The third line contains a single string with length $N$. For each valid $i$, the $i$-th character of the string is the letter written in the $i$-th node.
Two lines follow. The first line contains $M$ integers $u_{1},\ldots,u_{m}$. The second lines contains $M$ integers, $v_{1},\ldots,v_{m}$. This denotes that there is an edge connecting nodes $u_{i}$ and to $v_{i}$. These edges are distinct, even though they may connect the same pair of nodes.

------  Output ------
For each test case, print a single line containing one integer — the number of beautiful paths modulo $10^{9}+7$.

------  Constraints ------
$1 ≤ T ≤ 200$
$2 ≤ N ≤ 10^{3}$
$1 ≤ M ≤ 10^{3}$
$2 ≤ L ≤ 20$
$S$ contains only lowercase English letters
$1 ≤ u, v ≤ N$
$u \neq v$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2

4 4 3

aac

aaca

1 2 2 1

2 3 4 2

2 1 2

aa

aa

1

2
----- Sample Output 1 ------ 
3

1
----- explanation 1 ------ 
Example case 1: The three beautiful paths (sequences of edges) are:
- $(1,2)$, passing through nodes $(1,2,3)$ in this order
- $(4,2)$, also passing through nodes $(1,2,3)$
- $(3,2)$, passing through nodes $(4,2,3)$

Example case 2: There is only one beautiful path, which contains only edge $1$. Note that for this path (sequence of edges), there are two valid sequences of nodes: $(1,2)$ and $(2,1)$.

Difficulty: VERY_HARD
Tags: Graph algorithms

Number theory

Dynamic programming

Mathematics

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
import os, sys
from collections import defaultdict as dd, deque as dq, Counter as dc

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	(N, M, L) = getInts()
	counts = [0] * N
	G = [[[] for _ in range(26)] for _ in range(N)]
	S = listStr()
	vertex = listStr()
	U = [u - 1 for u in getInts()]
	V = [v - 1 for v in getInts()]
	orda = ord('a')
	extras_ = [dd(int)] * 26
	for i in range(M):
		(u, v) = (U[i], V[i])
		G[u][ord(vertex[v]) - orda].append(v)
		G[v][ord(vertex[u]) - orda].append(u)
		if vertex[u] == vertex[v]:
			extras_[ord(vertex[u]) - orda][min(u, v), max(u, v)] += 1
	for (i, v) in enumerate(vertex):
		if v == S[0]:
			counts[i] += 1
	for i in range(1, L):
		targ = ord(S[i]) - orda
		new_counts = [0] * N
		for j in range(N):
			for x in G[j][targ]:
				new_counts[x] += counts[j]
				new_counts[x] %= MOD
		counts = list(new_counts)
	ans = sum(counts)
	if len(set(S)) == 1:
		for (key, val) in extras_[ord(S[0]) - orda].items():
			ans -= pow(val, L - 1, MOD)
	return ans % MOD
for _ in range(getInt()):
	print(solve())


from collections import defaultdict as dd
import sys
input = sys.stdin.readline
mod = 1000000007
for _ in range(int(input())):
	(n, m, l) = map(int, input().split())
	s = input().strip()
	f = 1
	for i in range(1, l):
		if s[i] != s[0]:
			f = 0
			break
	c = input().strip()
	adj = dd(list)
	if f:
		cnt = [[0 for i in range(n)] for j in range(n)]
	u = list(map(int, input().split()))
	v = list(map(int, input().split()))
	for i in range(m):
		(_u, _v) = (u[i], v[i])
		_u -= 1
		_v -= 1
		adj[_u].append(_v)
		adj[_v].append(_u)
		if f:
			if _u > _v:
				(_u, _v) = (_v, _u)
			cnt[_u][_v] += 1
	dp = [[0 for i in range(l)] for i in range(n)]
	for i in range(n):
		if c[i] == s[l - 1]:
			dp[i][l - 1] = 1
	for j in range(l - 2, -1, -1):
		for i in range(n):
			if s[j] != c[i]:
				continue
			for x in adj[i]:
				dp[i][j] += dp[x][j + 1]
				dp[i][j] %= mod
	ans = 0
	for i in range(n):
		ans += dp[i][0]
		ans %= mod
	if f:
		for i in range(n):
			for j in range(i + 1, n):
				if c[i] == c[j] and c[i] == s[0]:
					ans -= pow(cnt[i][j], l - 1, mod)
					ans %= mod
	while ans < 0:
		ans += mod
	print(ans)


t = int(input())
mod = 1000000007
for _ in range(t):
	(n, m, l) = list(map(int, input().split()))
	s = input()
	v = input()
	e1 = list(map(int, input().split()))
	e2 = list(map(int, input().split()))
	adj = [[] for _ in range(n + 1)]
	count = {}
	for i in range(m):
		adj[e1[i] - 1].append(e2[i] - 1)
		adj[e2[i] - 1].append(e1[i] - 1)
		temp = [e1[i] - 1, e2[i] - 1]
		temp.sort()
		if tuple(temp) not in count:
			count[tuple(temp)] = 0
		count[tuple(temp)] += 1
	dp = [[0 for _ in range(l)] for _ in range(n)]
	for j in range(0, n):
		if s[0] == v[j]:
			dp[j][0] = 1
	for j in range(1, l):
		for i in range(0, n):
			if s[j] != v[i]:
				continue
			for k in adj[i]:
				dp[i][j] = (dp[i][j] + dp[k][j - 1]) % mod
	ans = 0
	for i in range(0, n):
		ans = (ans + dp[i][l - 1]) % mod
	if min(s) == max(s):
		for i in range(0, n):
			for j in range(i + 1, n):
				if v[i] == v[j] and (i, j) in count:
					ans = (ans - pow(count[i, j], l - 1, mod) + mod) % mod
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	(n, m, l) = inp()
	s = str(input())
	a = str(input())
	g = [[] for i in range(n)]
	dp = [[0] * l for i in range(n)]
	(b, c) = (inp(), inp())
	for (i, j) in zip(b, c):
		i -= 1
		j -= 1
		g[i].append(j)
		g[j].append(i)
	for i in range(n):
		if a[i] == s[0]:
			dp[i][0] = 1
	for i in range(1, l):
		for node in range(n):
			if a[node] == s[i]:
				for edge in g[node]:
					dp[node][i] += dp[edge][i - 1]
					dp[node][i] %= mod
	ans = 0
	for i in range(n):
		ans += dp[i][-1]
		ans %= mod
	if len(set(s)) == 1:
		mat = [[0] * n for i in range(n)]
		for i in range(m):
			mat[b[i] - 1][c[i] - 1] += 1
			mat[c[i] - 1][b[i] - 1] += 1
		for i in range(n):
			for j in range(i + 1, n):
				if mat[i][j] > 0 and a[i] == s[0] and (a[j] == s[0]):
					ans = (ans + mod - pow(mat[i][j], l - 1, mod)) % mod
	print(ans)


from collections import defaultdict
MOD = 10 ** 9 + 7

def solve():
	(N, M, L) = map(int, input().split())
	counts = [0] * N
	G = [[[] for _ in range(26)] for _ in range(N)]
	S = list(input())
	vertex = list(input())
	U = [u - 1 for u in list(map(int, input().split()))]
	V = [v - 1 for v in list(map(int, input().split()))]
	orda = ord('a')
	extras_ = [defaultdict(int)] * 26
	for i in range(M):
		(u, v) = (U[i], V[i])
		G[u][ord(vertex[v]) - orda].append(v)
		G[v][ord(vertex[u]) - orda].append(u)
		if vertex[u] == vertex[v]:
			extras_[ord(vertex[u]) - orda][min(u, v), max(u, v)] += 1
	for (i, v) in enumerate(vertex):
		if v == S[0]:
			counts[i] += 1
	for i in range(1, L):
		targ = ord(S[i]) - orda
		new_counts = [0] * N
		for j in range(N):
			for x in G[j][targ]:
				new_counts[x] += counts[j]
				new_counts[x] %= MOD
		counts = list(new_counts)
	ans = sum(counts)
	if len(set(S)) == 1:
		ans -= sum([pow(val, L - 1, MOD) for (key, val) in extras_[ord(S[0]) - orda].items()])
	return ans % MOD
for _ in range(int(input())):
	print(solve())