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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
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
 else:
  if(l.count(1)<m):
   generate(n,m,l+[1])
   if(l.count(0)<n):
    generate(n,m,l+[0])
  else:
   if(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]
 # 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)


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]
 # print(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
  # num_blocks += 1
  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


def find_interleavings_2(a, b, i, j):
 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)

 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

 ils = find_interleavings_2(a, b, 0, 0)
 ils = [tuple(x) for x in ils]
 # print(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
  # num_blocks += 1
  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)
 # print(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
  # num_blocks += 1
  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)
 #print(ils)
 for c in ils:
  num_blocks = 0
  prev = math.inf
  for i in c:
   if i != prev:
    num_blocks += 1
   prev = i
  # num_blocks += 1
  if num_blocks == k:
   res += 1
 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)
 #print(ils)
 for c in ils:
  num_blocks = 0
  prev = math.inf
  for i in c:
   if i != prev:
    num_blocks += 1
   prev = i
  # num_blocks += 1
  if num_blocks == k:
   res += 1
 print(res)


# cook your dish here
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
 else:
  if(l.count(1)<m):
   generate(n,m,l+[1])
   if(l.count(0)<n):
    generate(n,m,l+[0])
  else:
   if(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)


# cook your dish here
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
 else:
  if(l.count(1)<m):
   generate(n,m,l+[1])
   if(l.count(0)<n):
    generate(n,m,l+[0])
  else:
   if(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)


# cook your dish here
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
 else:
  if(l.count(1)<m):
   generate(n,m,l+[1])
   if(l.count(0)<n):
    generate(n,m,l+[0])
  else:
   if(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)


# cook your dish here
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
 else:
  if(l.count(1)<m):
   generate(n,m,l+[1])
   if(l.count(0)<n):
    generate(n,m,l+[0])
  else:
   if(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)


# cook your dish here
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()))

 # 0: m end, 1: n end
 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):
   # m end
   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)
    
   # n end
   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)


# cook your dish here
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()))

 # 0: m end, 1: n end
 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):
   # m end
   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)
    
   # n end
   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)


# cook your dish here
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()))

 # 0: m end, 1: n end
 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):
   # m end
   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)
    
   # n end
   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)