#include <bits/stdc++.h>
using namespace std;
const int DIM = 505;
const int INF = 1005;
const int MOD = 666013;
int n, m, p;
int dp[DIM][105];
int p1[DIM], p2[DIM];
int s1[DIM], s2[DIM], s3[105];
int aib[2][DIM][DIM];
void update(int l, int x, int y, int val) {
++x; ++y;
for (int i = x; i <= n + 1 ; i += (i & (-i))) {
for (int j = y; j <= m + 1 ; j += (j & (-j))) {
aib[l][i][j] += val;
if (aib[l][i][j] >= MOD) aib[l][i][j] -= MOD;
}
}
}
int query(int l, int x, int y) {
int ans = 0;
++x; ++y;
for (int i = x; i > 0 ; i -= (i & (-i))) {
for (int j = y; j > 0 ; j -= (j & (-j))) {
ans += aib[l][i][j];
if (ans >= MOD) ans -= MOD;
}
}
return ans;
}
bool cmp1(int x, int y) {
if (s1[x] != s1[y]) return s1[x] < s1[y];
return x < y;
}
bool cmp2(int x, int y) {
if (s2[x] != s2[y]) return s2[x] < s2[y];
return x < y;
}
int main()
{
freopen("pedefe.in", "r", stdin);
freopen("pedefe.out", "w", stdout);
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n ; ++i) scanf("%d", &s1[i]), p1[i] = i;
for (int i = 1; i <= m ; ++i) scanf("%d", &s2[i]), p2[i] = i;
for (int i = 1; i <= p ; ++i) scanf("%d", &s3[i]);
sort(p1 + 1, p1 + n + 1, cmp1);
sort(p2 + 1, p2 + m + 1, cmp2);
s3[p + 1] = INF;
update(0, 0, 0, 1);
int Sol = 0;
for (int k = 1, l = 0; k <= p + 1 ; ++k, l = 1 - l) {
memset(aib[1 - l], 0, sizeof(aib[1 - l]));
for (int i = 1; i <= n ; ++i) {
if (s1[p1[i]] >= s3[k]) break ;
for (int j = 1; j <= m ; ++j) {
if (s2[p2[j]] >= s3[k]) break ;
if (s1[p1[i]] == s2[p2[j]] && s1[p1[i]] >= s3[k - 1] && s1[p1[i]] < s3[k]) {
dp[p1[i]][p2[j]] = query(l, p1[i] - 1, p2[j] - 1);
update(l, p1[i], p2[j], dp[p1[i]][p2[j]]);
}
}
}
if (k == p + 1) {
printf("%d", query(l, n, m));
return 0;
}
for (int i = n; i >= 1 ; --i) {
for (int j = m; j >= 1 ; --j) {
if (s1[i] == s2[j] && s1[i] == s3[k]) {
dp[i][j] = query(l, i - 1, j - 1);
update(1 - l, i, j, dp[i][j]);
}
}
}
}
return 0;
}