// Translated from Vincent.java

#include <iostream>

using namespace std;

	const long long P = 999999937;
	const int N_SIZE = 500010;
	int order[3][N_SIZE];
	int pos[3][N_SIZE]; // # position of node n in preorder, postorder
	int child[3][N_SIZE]; // #left child, right child, parent; undetermined children are both left and right children
	int desc[3][N_SIZE]; // #descendants constrainted to be < node , > node, [no constraint]
	int borders[N_SIZE];
	int N;

	long long inverse(long long a, long long mod) {
		long long M = mod;
		long long u = 1, U = 0, v = 0, V = 1;
		while (a != 0) {
			long long q = mod / a;
			long long r = mod % a;
			mod = a;
			a = r;
			long long U2 = U - q * u;
			long long V2 = V - q * v;
			U = u;
			V = v;
			u = U2;
			v = V2;
		}
		return (U + M) % M;
	}

	long long binom(long long mod, int k, int n) {
		if (k < 0 || k > n) {
			return 0;
		} else if (2 * k > n) {
			return binom(mod, n - k, n);
		}
		long long num = 1;
		long long denom = 1;
		for (int i = 0; i < k; i++) {
			num = (num * (n - i)) % mod;
			denom = (denom * (i+1)) % mod;
		}
		return (num * inverse(denom, mod)) % mod;
	}

    int main() {
        ios_base::sync_with_stdio(false);
        cin>>N;

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < N; j++) {
				cin>>order[i][j];
				order[i][j]--;
			}
		}
		for (int j = 0; j < N; j++) {
			for (int i = 0; i < 3; i++) {
				child[i][j] = -1;
			}
			pos[2][j] = -1;
		}
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < N; j++) {
				if (order[i][j] != -1) {
					pos[i][order[i][j]] = j;
				}
			}
		}
		for (int j = 0; j < N - 1; j++) {
			if (pos[1][order[0][j + 1]] < pos[1][order[0][j]]) {
				child[0][order[0][j]] = order[0][j + 1];
				child[2][order[0][j + 1]] = order[0][j];
			}
		}
		for (int j = 1; j < N; j++) {
			if (pos[0][order[1][j - 1]] > pos[0][order[1][j]]) {
				child[1][order[1][j]] = order[1][j - 1];
				child[2][order[1][j - 1]] = order[1][j];
			}
		}
		for (int i = 0; i < N; i++) {
			int l = child[0][i];
			int r = child[1][i];
			if (l == r && l != -1 && pos[2][i] != -1 && pos[2][l] != -1) {
				if (pos[2][i] < pos[2][l]) {
					child[0][i] = -1;
				} else {
					child[1][i] = -1;
				}
			}
		}

		int L = -1;
		int R = -1;
		int F = -1;
		for (int i = 0; i < N; i++) {
			if (order[2][i] != -1) {
				R = order[2][i];
				if (L == -1) {
					L = order[2][i];
				}
			}
		}
		for (int n = L; n != -1; n = child[2][n]) {
			borders[n]++;
		}
		for (int n = R; n != -1; n = child[2][n]) {
			borders[n]++;
			if (borders[n] == 2 && F == -1) {
				F = n;
			}
		}
		for (int n = L; n != F; n = child[2][n]) {
			int p = child[2][n];
			if (pos[2][p] == -1 && child[0][p] == n) {
				child[0][p] = -1;
			} else if (pos[2][p] != -1 && child[1][p] == n) {
				child[1][p] = -1;
			}
		}
		for (int n = R; n != F; n = child[2][n]) {
			int p = child[2][n];
			if (pos[2][p] == -1 && child[1][p] == n) {
				child[1][p] = -1;
			} else if (pos[2][p] != -1 && child[0][p] == n) {
				child[0][p] = -1;
			}
		}
		if (L != R && child[0][L] == child[1][L]) {
			child[1][L] = -1;
		}
		if (L != R && child[0][R] == child[1][R]) {
			child[0][R] = -1;
		}
		for (int i = 0; i < N; i++) {
			int n = order[1][i];
			int l = child[0][n];
			int r = child[1][n];
			if (l == -1 && r == -1) {
				desc[2][n] = 1;
			} else if (l == r) {
				desc[2][n] = desc[2][l] + 1;
			} else {
				desc[0][n] = l == -1 ? 0 : desc[2][l];
				desc[1][n] = r == -1 ? 0 : desc[2][r];
				desc[2][n] = desc[0][n] + desc[1][n] + 1;
			}
		}
		int undetermined = 0;
		for (int i = 0; i < N; i++) {
			if (child[0][i] == child[1][i] && child[0][i] != -1) {
				//System.err.println(i + " has a unique child");
				undetermined++;
			}
		}
		int before = 0;
		int target = 0;
		int chain = 0;
		if (F != -1) {
			before = desc[0][F];
			target = pos[2][F];
			int c = F;
			for (int n = child[2][F]; n != -1; n = child[2][n]) {
				if (child[0][n] == child[1][n]) {
					chain++;
				} else if (child[0][n] != c) {
					before += desc[0][n] + 1;
				}
				c = n;
			}
		}
		long long result = 1;
		if (L == R && F != -1 && child[0][F] != -1 && child[0][F] == child[1][F]) {
			undetermined--;
			result = binom(P, target - before, chain) + binom(P, target - before - desc[2][F] + 1, chain);
		} else if (F != -1) {
			result = binom(P, target - before, chain);
		}
		for (int i = chain; i < undetermined; i++) {
			result = (result << 1) % P;
		}
		cout<<result<<endl;


        return 0;
    }