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$.
import math


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
 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]
 #print(ils, numBlo)
 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)], 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
 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]
 #print(ils, numBlo)
 memo = dict()
 for c in numBlo:
  if c == k:
   res += 1

 print(res)
