#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

ifstream fi("pedefe.in");
ofstream fo("pedefe.out");

const int MOD = 666013, N = 505;

template<int MOD>
class Num {
public:
	int val;

	Num(int _val) {
		val = _val % MOD;
		val = val < 0 ? val + MOD : val; }

	Num(long long _val) {
		val = _val % MOD;
		val = val < 0 ? val + MOD : val; }
	Num() : val(0) { }

	inline Num operator + (const Num &arg) const {
		Num res;
		res.val = val + arg.val;
		res.val = res.val >= MOD ? res.val - MOD : res.val;
		return res; }

	inline Num operator - (const Num &arg) const {
		Num res;
		res.val = val - arg.val;
		res.val = res.val < 0 ? res.val + MOD : res.val;
		return res; }

	inline Num operator - () const {
		Num res;
		res.val = MOD - res.val;
		res.val = res.val == MOD ? 0 : res.val;
		return res; }

	inline Num operator * (const Num &arg) const {
		return Num(1LL * val * arg.val); }

	inline void operator += (const Num &arg) {
		(*this) = (*this) + arg; }

	inline void operator -= (const Num &arg) {
		(*this) = (*this) - arg; }

	inline void operator *= (const Num &arg) {
		(*this) = (*this) * arg; } };

template<int MOD>
ostream &operator << (ostream &fo, const Num<MOD> &c) {
	fo << c.val;
	return fo; }

template<int MOD>
istream &operator >> (istream &fi, Num<MOD> &c) {
	fi >> c.val;
	c = Num<MOD>(c.val);
	return fi; }


vector<vector<Num<MOD>>> dp[2];
int s0[N], s1[N], s2[N];

vector<int> alph;
int n, m, p;

static void enforced(int ch) {
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j) if (s1[i] == s2[j] && s1[i] == ch)
		dp[1][i][j] = dp[0][i - 1][j - 1];

	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
		dp[1][i][j]+= dp[1][i - 1][j] + dp[1][i][j - 1] - dp[1][i - 1][j - 1]; }

static void unenforced(int ch, bool pula) {
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j) {
		if (s1[i] == s2[j] && s1[i] == ch)
			dp[1][i][j] = dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1];
		dp[1][i][j]+= dp[1][i - 1][j] + dp[1][i][j - 1] - dp[1][i - 1][j - 1]; }

	if (pula)
		return;

	for (int i = 0; i <= n; ++i)
	for (int j = 0; j <= m; ++j)
		dp[1][i][j]+= dp[0][i][j]; }


int main() {
	int ptr(1);

	fi >> n >> m >> p;
	for (int i = 1; i <= n; ++i) {
		fi >> s1[i];
		alph.push_back(s1[i]); }
	for (int i = 1; i <= m; ++i) {
		fi >> s2[i];
		alph.push_back(s2[i]); }
	for (int i = 1; i <= p; ++i) {
		fi >> s0[i];
		alph.push_back(s0[i]); }

	if (!is_sorted(s0 + 1, s0 + p + 1)) {
		fo << "0\n";
		return 0;  }

	dp[0] = dp[1] = vector<vector<Num<MOD>>>(n + 5, vector<Num<MOD>>(m + 5));
	sort(begin(alph), end(alph));
	alph.erase(unique(begin(alph), end(alph)), end(alph));

	for (auto &line: dp[1])
			fill(begin(line), end(line), 1);

	for (int k = 0; k < alph.size(); ++k) {
		swap(dp[0], dp[1]);
		if (alph[k] == s0[ptr]) {

			if (s0[ptr] == s0[ptr + 1]) {
				enforced(alph[k]);
				k-= 1; }
			else
				unenforced(alph[k], true);

			ptr+= 1;}
		else {
			unenforced(alph[k], false); }

		for (auto &line: dp[0])
			fill(begin(line), end(line), 0); }

	cerr << dp[1][n][m] << endl;
	fo << dp[1][n][m] << endl;

	return 0; }