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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def find_interleavings_2(a, b, i, j):\n try:\n  return lev_memo[(i, j)], nbs_memo[(i, j)]\n except KeyError:\n  pass\n to_return = []\n nbs = []\n if i == len(a) and j == len(b):\n  return [[]], [0]\n elif i == len(a):\n  leaves, nbs1 = find_interleavings_2(a, b, i, j + 1)\n  for ind in range(len(leaves)):\n   leaf = leaves[ind]\n   to_return.append([b[j]] + leaf)\n   if len(leaf) == 0:\n    nbs.append(nbs1[ind] + 1)\n   elif leaf[0] == b[j]:\n    nbs.append(nbs1[ind])\n   else:\n    nbs.append(nbs1[ind] + 1)\n elif j == len(b):\n  leaves, nbs1 = find_interleavings_2(a, b, i + 1, j)\n  for ind in range(len(leaves)):\n   leaf = leaves[ind]\n   to_return.append([a[i]] + leaf)\n   if len(leaf) == 0:\n    nbs.append(nbs1[ind] + 1)\n   elif leaf[0] == a[i]:\n    nbs.append(nbs1[ind])\n   else:\n    nbs.append(nbs1[ind] + 1)\n else:\n  leaves, nbs1 = find_interleavings_2(a, b, i, j + 1)\n  for ind in range(len(leaves)):\n   leaf = leaves[ind]\n   to_return.append([b[j]] + leaf)\n   if len(leaf) == 0:\n    nbs.append(nbs1[ind] + 1)\n   elif leaf[0] == b[j]:\n    nbs.append(nbs1[ind])\n   else:\n    nbs.append(nbs1[ind] + 1)\n\n  leaves2, nbs2 = find_interleavings_2(a, b, i + 1, j)\n  for ind in range(len(leaves2)):\n   leaf = leaves2[ind]\n   to_return.append([a[i]] + leaf)\n   if len(leaf) == 0:\n    nbs.append(nbs1[ind] + 1)\n   elif leaf[0] == a[i]:\n    nbs.append(nbs2[ind])\n   else:\n    nbs.append(nbs2[ind] + 1)\n\n lev_memo[(i, j)] = to_return\n nbs_memo[(i, j)] = nbs\n to_remove_lev = []\n to_remove_nbs = []\n for nbi in range(len(nbs)):\n  if nbs[nbi] > k:\n   to_remove_lev.append(to_return[nbi])\n   to_remove_nbs.append(nbs[nbi])\n\n for tri in to_remove_lev:\n  to_return.remove(tri)\n for tri in to_remove_nbs:\n  nbs.remove(tri)\n return to_return, nbs\n\n\nfor _ in range(int(input())):\n n, m, k = list(map(int, input().split(" ")))\n a = list(map(int, input().split(" ")))\n b = list(map(int, input().split(" ")))\n res = 0\n\n lev_memo = dict()\n nbs_memo = dict()\n ils, numBlo = find_interleavings_2(a, b, 0, 0)\n ils = [tuple(x) for x in ils]\n # print(ils, numBlo)\n memo = dict()\n for c in numBlo:\n  if c == k:\n   res += 1\n\n print(res)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15477