In an array, a $block$ is a maximal sequence of identical elements. Since blocks are maximal, adjacent blocks have distinct elements, so the array breaks up into a series of blocks.  For example, given the array $[3, 3, 2, 2, 2, 1, 5, 8, 4, 4]$, there are 6 blocks: $[3, 3], [2, 2, 2], [1], [5], [8], [4, 4]$ . 
In this task, you are given two arrays, $A$ (of length $n$), and $B$ (of length $m$), and a number $K$. You have to interleave $A$ and $B$ to form an array $C$ such that $C$ has $K$ blocks. Each way of interleaving $A$ and $B$ can be represented as a $0-1$ array $X$ of length $n+m$ in which $X[j]$ is $0$ if $C[j]$ came from $A$ and $X[j]$ is $1$ if $C[j]$ came from $B$.
A formal description of the interleaving process is given at the end.
For example, if $A = [1, 3]$ and $B = [3, 4]$, there are $6$ ways of interleaving $A$ and $B$.  With each interleaving $X$ of $A$ and $B$, we also count the number of blocks in the resulting interleaved array $C$.  The descriptions of the interleavings, $X$, and the outcomes, $C$, are given below.
- $X = [0, 0, 1, 1]$, which corresponds to $C = [1, 3, 3, 4]$, $3$ blocks.
- $X = [0, 1, 0, 1]$, which corresponds to $C = [1, 3, 3, 4]$, $3$ blocks.
- $X = [0, 1, 1, 0]$, which corresponds to $C = [1, 3, 4, 3]$ , $4$ blocks.
- $X = [1, 0, 0, 1]$, which corresponds to $C = [3, 1, 3, 4]$, $4$ blocks.
- $X = [1, 0, 1, 0]$, which corresponds to $C = [3, 1, 4, 3]$, $4$ blocks.
- $X = [1, 1, 0, 0]$, which corresponds to $C = [3, 4, 1, 3]$, $4$ blocks.
Observe that different interleavings $X$ may produce the same array $C$, such as the first two interleavings in the example above.
Your task is the following.  Given arrays $A$ and $B$ and a number $K$, find the number of different interleavings $X$ of $A$ and $B$ that produce an output array $C$ with exactly $K$ blocks.  Note that we are counting the number of interleavings, not the number of different output arrays after interleaving.  For instance, if the same output array C is produced via 2 different interleavings, it gets counted twice.
Since the answer might be large, print the answer modulo $10^8 + 7$.
Here is a formal definition of the interleaving process:
Suppose $A = A_1, A_2, ..., A_n$ and $B = B_1, B_2, ..., B_m$. Then, the process of generating an interleaving $C$ can be described using an array $X$ of size $n + m$, with exactly $n$ $0's$ and $m$ $1's$.  Suppose we have such an array $X = X_1, X_2, ..., X_{n+m}$. Using this array $X$, we create the output array $C = C_1, C_2, ..., C_{n+m}$, using the following algorithm:
i = 0, j = 0
while( (i+j)<(n+m) )
if(X[i+j+1] == 0)
C[i+j+1] = A[i+1]
i = i+1
else
C[i+j+1] = B[j+1]
j = j+1

Thus if the $X$ value is $0$, we pick the next available element from $A$ into $C$, and if it is $1$, we pick from $B$ instead. This creates an interleaving of the arrays $A$ and $B$.

-----Input Format:-----
- The first line contains a single integer, $T$, which is the number of testcases. The description of each testcase follows.
- The first line of each testcase contains three integers: $n$, $m$, and $K$, which denote the size of array $A$, the size of array $B$, and the required number of blocks in $C$, respectively.
- The next line contains $n$ integers, which represent the array $A$.
- The next line contains $m$ integers, which represent the array $B$.

-----Output Format:-----
- You should print the answer in a new line for each testcase, which should be the number of valid interleaving arrays $X$ which correspond to an output array $C$ with $K$ blocks, modulo $10^8 + 7$.

-----Constraints:-----
- $1 \leq T \leq 10$
- $1 \leq n \leq 100$
- $1 \leq m \leq 100$
- $1 \leq K \leq n+m$
- $0 \leq A_i, B_j \leq 10^9$

-----Subtasks:-----
- Subtask 1: 10% points: $m = 1$
- Subtask 2: 30% points: $0 \leq A_i, B_j \leq 1$
- Subtask 3: 60% points: Original constraints.

-----Sample Input:-----
5
2 2 4
1 3
3 4
2 2 3
1 3
3 4
2 2 2
1 3
3 4
2 2 4
4 7
8 5
2 2 2
4 7
8 5

-----Sample Output:-----
4
2
0
6
0

-----Explanation:-----
- The first three testcases correspond to the example given in the problem statement. Of the $6$ interleavings, $4$ produce outputs with $4$ blocks and $2$ produce outputs with $3$ blocks.  Hence, for $K = 4$, the answer is $4$, for $K = 3$, the answer is $2$, and for $K = 2$, the answer is $0$.
- The fourth and fifth testcases have $A = [4, 7]$ and $B = [8, 5]$.  Here are the $6$ interleavings of these two arrays.
- $X = [0, 0, 1, 1]$, which corresponds to $C= [4, 7, 8, 5]$, $4$ blocks.
- $X = [0, 1, 0, 1]$, which corresponds to $C= [4, 8, 7, 5]$, $4$ blocks.
- $X = [0, 1, 1, 0]$, which corresponds to $C= [4, 8, 5, 7]$, $4$ blocks.
- $X = [1, 0, 0, 1]$, which corresponds to $C= [8, 4, 7, 5]$, $4$ blocks.
- $X = [1, 0, 1, 0]$, which corresponds to $C= [8, 4, 5, 7]$, $4$ blocks.
- $X = [1, 1, 0, 0]$, which corresponds to $C= [8, 5, 4, 7]$, $4$ blocks.
All $6$ interleavings produce outputs with $4$ blocks, so for $K = 4$ the answer is $6$ and for any other value of $K$, the answer is $0$.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n = 0
m = 0
A = []
B = []
anscount = 0
k = 0

def generate(n, m, l):
	nonlocal anscount
	if len(l) == n + m:
		X = l
		(i, j) = (0, 0)
		C = [0 for t in range(n + m)]
		while i + j < n + m:
			if X[i + j] == 0:
				C[i + j] = A[i]
				i = i + 1
			else:
				C[i + j] = B[j]
				j = j + 1
		ans = len(C)
		for i in range(1, len(C)):
			if C[i] == C[i - 1]:
				ans -= 1
		if ans == k:
			anscount += 1
	elif l.count(1) < m:
		generate(n, m, l + [1])
		if l.count(0) < n:
			generate(n, m, l + [0])
	elif l.count(0) < n:
		generate(n, m, l + [0])
for _ in range(int(input())):
	anscount = 0
	(n, m, k) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	generate(n, m, [])
	print(anscount)


def find_interleavings_2(a, b, i, j):
	try:
		return (lev_memo[i, j], nbs_memo[i, j])
	except KeyError:
		pass
	to_return = []
	nbs = []
	if i == len(a) and j == len(b):
		return ([[]], [0])
	elif i == len(a):
		(leaves, nbs1) = find_interleavings_2(a, b, i, j + 1)
		for ind in range(len(leaves)):
			leaf = leaves[ind]
			to_return.append([b[j]] + leaf)
			if len(leaf) == 0:
				nbs.append(nbs1[ind] + 1)
			elif leaf[0] == b[j]:
				nbs.append(nbs1[ind])
			else:
				nbs.append(nbs1[ind] + 1)
	elif j == len(b):
		(leaves, nbs1) = find_interleavings_2(a, b, i + 1, j)
		for ind in range(len(leaves)):
			leaf = leaves[ind]
			to_return.append([a[i]] + leaf)
			if len(leaf) == 0:
				nbs.append(nbs1[ind] + 1)
			elif leaf[0] == a[i]:
				nbs.append(nbs1[ind])
			else:
				nbs.append(nbs1[ind] + 1)
	else:
		(leaves, nbs1) = find_interleavings_2(a, b, i, j + 1)
		for ind in range(len(leaves)):
			leaf = leaves[ind]
			to_return.append([b[j]] + leaf)
			if len(leaf) == 0:
				nbs.append(nbs1[ind] + 1)
			elif leaf[0] == b[j]:
				nbs.append(nbs1[ind])
			else:
				nbs.append(nbs1[ind] + 1)
		(leaves2, nbs2) = find_interleavings_2(a, b, i + 1, j)
		for ind in range(len(leaves2)):
			leaf = leaves2[ind]
			to_return.append([a[i]] + leaf)
			if len(leaf) == 0:
				nbs.append(nbs1[ind] + 1)
			elif leaf[0] == a[i]:
				nbs.append(nbs2[ind])
			else:
				nbs.append(nbs2[ind] + 1)
	lev_memo[i, j] = to_return
	nbs_memo[i, j] = nbs
	to_remove_lev = []
	to_remove_nbs = []
	for nbi in range(len(nbs)):
		if nbs[nbi] > k:
			to_remove_lev.append(to_return[nbi])
			to_remove_nbs.append(nbs[nbi])
	for tri in to_remove_lev:
		to_return.remove(tri)
	for tri in to_remove_nbs:
		nbs.remove(tri)
	return (to_return, nbs)
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	res = 0
	lev_memo = dict()
	nbs_memo = dict()
	(ils, numBlo) = find_interleavings_2(a, b, 0, 0)
	ils = [tuple(x) for x in ils]
	memo = dict()
	for c in numBlo:
		if c == k:
			res += 1
	print(res)


import math

def find_interleavings_2(a, b, i, j):
	try:
		return lev_memo[i, j]
	except KeyError:
		pass
	to_return = []
	if i == len(a) and j == len(b):
		return [[]]
	elif i == len(a):
		for leaf in find_interleavings_2(a, b, i, j + 1):
			to_return.append([b[j]] + leaf)
	elif j == len(b):
		for leaf in find_interleavings_2(a, b, i + 1, j):
			to_return.append([a[i]] + leaf)
	else:
		for leaf in find_interleavings_2(a, b, i, j + 1):
			to_return.append([b[j]] + leaf)
		for leaf in find_interleavings_2(a, b, i + 1, j):
			to_return.append([a[i]] + leaf)
	lev_memo[i, j] = to_return
	return to_return
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	res = 0
	lev_memo = dict()
	ils = find_interleavings_2(a, b, 0, 0)
	ils = [tuple(x) for x in ils]
	memo = dict()
	for c in ils:
		try:
			res += memo[c]
			continue
		except KeyError:
			pass
		num_blocks = 0
		prev = math.inf
		for i in c:
			if i != prev:
				num_blocks += 1
			prev = i
		if num_blocks == k:
			res += 1
			memo[c] = 1
		else:
			memo[c] = 0
	print(res)


import math

def find_interleavings(a, b):
	c = list()

	def interleaf(i, j, l):
		if i == len(a) and j == len(b):
			c.append(tuple(l))
		elif i == len(a):
			interleaf(i, j + 1, l + [b[j]])
		elif j == len(b):
			interleaf(i + 1, j, l + [a[i]])
		else:
			interleaf(i + 1, j, l + [a[i]])
			interleaf(i, j + 1, l + [b[j]])
	interleaf(0, 0, [])
	return c
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	res = 0
	ils = find_interleavings(a, b)
	memo = dict()
	for c in ils:
		try:
			res += memo[c]
			continue
		except KeyError:
			pass
		num_blocks = 0
		prev = math.inf
		for i in c:
			if i != prev:
				num_blocks += 1
			prev = i
		if num_blocks == k:
			res += 1
			memo[c] = 1
		else:
			memo[c] = 0
	print(res)


import math

def find_interleavings(a, b):
	c = list()

	def interleaf(i, j, l):
		if i == len(a) and j == len(b):
			c.append(l)
		elif i == len(a):
			interleaf(i, j + 1, l + [b[j]])
		elif j == len(b):
			interleaf(i + 1, j, l + [a[i]])
		else:
			interleaf(i + 1, j, l + [a[i]])
			interleaf(i, j + 1, l + [b[j]])
	interleaf(0, 0, [])
	return c
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	res = 0
	ils = find_interleavings(a, b)
	for c in ils:
		num_blocks = 0
		prev = math.inf
		for i in c:
			if i != prev:
				num_blocks += 1
			prev = i
		if num_blocks == k:
			res += 1
	print(res)


mod = 10 ** 8 + 7

def dic_add(dic, k1, v):
	if k1 <= k:
		if k1 in dic:
			dic[k1] = (dic[k1] + v) % mod
		else:
			dic[k1] = v
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	a_l = list(map(int, input().split()))
	b_l = list(map(int, input().split()))
	f_dp = [[[{} for _ in range(n + 1)] for _ in range(m + 1)] for _ in range(2)]
	f_dp[0][1][0] = {1: 1}
	f_dp[1][0][1] = {1: 1}
	dif = 1
	for j in range(1, m):
		if b_l[j] != b_l[j - 1]:
			dif += 1
		f_dp[0][j + 1][0] = {dif: 1}
	dif = 1
	for i in range(1, n):
		if a_l[i] != a_l[i - 1]:
			dif += 1
		f_dp[1][0][i + 1] = {dif: 1}
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if j - 2 >= 0 and b_l[j - 1] != b_l[j - 2]:
				addi = 1
			else:
				addi = 0
			for (kk, vv) in list(f_dp[0][j - 1][i].items()):
				dic_add(f_dp[0][j][i], kk + addi, vv)
			if b_l[j - 1] != a_l[i - 1]:
				addi = 1
			else:
				addi = 0
			for (kk, vv) in list(f_dp[1][j - 1][i].items()):
				dic_add(f_dp[0][j][i], kk + addi, vv)
			if i - 2 >= 0 and a_l[i - 1] != a_l[i - 2]:
				addi = 1
			else:
				addi = 0
			for (kk, vv) in list(f_dp[1][j][i - 1].items()):
				dic_add(f_dp[1][j][i], kk + addi, vv)
			if b_l[j - 1] != a_l[i - 1]:
				addi = 1
			else:
				addi = 0
			for (kk, vv) in list(f_dp[0][j][i - 1].items()):
				dic_add(f_dp[1][j][i], kk + addi, vv)
	ans = 0
	if k in f_dp[0][m][n]:
		ans += f_dp[0][m][n][k]
	if k in f_dp[1][m][n]:
		ans += f_dp[1][m][n][k]
	print(ans % mod)