//#pragma GCC optimize("Ofast,unroll-loops")

#ifdef LOCAL
#include "debug.h"
#else
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x...)
#endif

using namespace std;

#define int ll

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
#define sz(x) int((x).size())

template <typename T>
using ordered_set = __gnu_pbds::tree <T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

#ifdef ONLINE_JUDGE
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#else
mt19937 rng(1000 - 7);
#endif

const int N = 6;
const int M = 1e3 + 10;
//const int MOD = 998244353;
const ll MOD = 1e9 + 9;
const ld eps = 5e-8;
const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

int n, m, k;
int a[N][M], dp[M][(1 << N)];

inline int get(int x, int i) {
    return x >> i & 1;
}

bool check(int j, int x, int y) {
    if (get(y, 0) && !get(y, 1) || get(y, n - 1) && !get(y, n - 2)) {
        return false;
    }
    for (int i = 1; i < n - 1; i++) {
        if (get(y, i) && !get(y, i - 1) && !get(y, i + 1)) {
            return false;
        }
    }

    for (int i = 1; i < n; i++) {
        if (get(y, i) && get(y, i - 1) && (get(x, i) || get(x, i - 1))) {
            return false;
        }
        if (get(y, i) && get(y, i - 1) &&
            (a[j][i] || a[j + 1][i] || a[j][i - 1] || a[j + 1][i - 1])) {
                return false;
            }
    }

    return true;
}

inline void relax(int& x, int y) {
    x = (x + y) % MOD;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout << fixed << setprecision(9);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        a[y - 1][x - 1] = 1;
    }

    dp[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int mask1 = 0; mask1 < (1 << n); mask1++) {
            bool flag = true;
            for (int j = 0; j < n && flag; j++) {
                if (get(mask1, j) && a[i][j]) {
                    flag = false;
                }
            }

            if (!flag) {
                continue;
            }

            if (mask1) {
                relax(dp[i][mask1], dp[i][0]);
            }

            debug(i, mask1, dp[i][mask1]);

            for (int mask2 = 0; mask2 < (1 << n); mask2++) {
                if (!check(i, mask1, mask2)) {
                    continue;
                }

                relax(dp[i + 1][mask2], dp[i][mask1]);
            }
        }
    }

    cout << dp[m][0] << endl;

    return 0;
}