#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const char iname[] = "pedefe.in";
const char oname[] = "pedefe.out";
#define MAXN 32
#define FOR(i, a, b) for (int i = (a); i < (b); ++ i)
#define FORi(i, G) for (vector <int>::iterator i = G.begin(); i != G.end(); ++ i)
int A[MAXN], B[MAXN], C[MAXN];
vector <int> G[MAXN];
int Ret;
void f(int i, int n, int j, int m, int k, int p, int lastval)
{
if (i == n) {
Ret += (k == p);
if (Ret >= 666013)
Ret -= 666013;
} else {
if (A[i] >= lastval)
FORi (it, G[i]) if (*it >= j)
f(i + 1, n, *it + 1, m, ((A[i] == C[k]) ? k + 1 : k), p, A[i]);
f(i + 1, n, j, m, k, p, lastval);
}
}
int main(void)
{
ifstream fin(iname);
int n, m, p;
fin >> n >> m >> p;
FOR (i, 0, n)
fin >> A[i];
FOR (i, 0, m)
fin >> B[i];
FOR (i, 0, p)
fin >> C[i];
fin.close();
FOR (i, 0, n) FOR (j, 0, m) if (A[i] == B[j])
G[i].push_back(j);
f(0, n, 0, m, 0, p, 0);
ofstream fout(oname);
fout << Ret << '\n';
fout.close();
return 0;
}