#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class AxonometricProjection {
public:
    int howManyWays(vector <int>, vector <int>);
};

const long long MD = 1000000009LL;
const int maxN = 60;

long long powmod(long long a, long long n) {
    if (n == 0) return 1LL;
    long long b = powmod(a, n / 2);
    b = (b * b) % MD;
    if (n % 2 == 0) return b;
    return (a * b) % MD;
}

int a[maxN], b[maxN], c[maxN][maxN];
int n, m;

long long solve() {
    int r = 0, s = 0;
    long long res = 1;
    for (int p = 10000; p >= 0; p --) {
        int x = 0, y = 0;
        for (int i = 0; i < n; i ++)
            if (a[i] == p) x ++;
        for (int i = 0; i < m; i ++)
            if (b[i] == p) y ++;

        int u = x + r, v = y + s;
        r += x, s += y;

        long long cur = 0;
        for (int i = 0; i <= x; i ++)
            for (int j = 0; j <= y; j ++) {
                int z = i * v + j * u - i * j;
                int t = x * v + y * u - x * y - z;
                long long A = powmod(p, z);
                long long B = powmod(p + 1, t);
                long long C = (A * B) % MD;
                C *= c[x][i], C %= MD;
                C *= c[y][j], C %= MD;
                if ((i + j) % 2 == 0) cur += C; else cur -= C;
            }
        cur %= MD;
        if (cur < 0) cur += MD;
        res *= cur, res %= MD;
    }
    return res;
}

int AxonometricProjection::howManyWays(vector <int> heightsOfLeftView, vector <int> heightsOfFrontView) {
    n = heightsOfLeftView.size();
    m = heightsOfFrontView.size();
    for (int i = 0; i <= 50; i ++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j ++)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MD;
    }
    for (int i = 0; i < n; i ++)
        a[i] = heightsOfLeftView[i];
    for (int i = 0; i < m; i ++)
        b[i] = heightsOfFrontView[i];
    return solve();
}

<%:testing-code%>
//Powered by [KawigiEdit] 2.0!