Untitled

#include <iostream>

using namespace std;

int n, m, k;
char map[10000][10000];
int answer = 0;

inline void print(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << map[i][j];    
        }    
        cout << endl;
    }    
}

void paint(int box){
    if(box == m*n){
        //print();
        //cout << "--" << endl;
        bool valid = true;
        for(int i = 0; i < n-1; i++){
            for(int j = 0; j < m-1; j++){
                int count = 0;
                if(map[i][j] == 'R') count ++;
                if(map[i][j+1] == 'R') count ++;
                if(map[i+1][j] == 'R') count ++;
                if(map[i+1][j+1] == 'R') count ++;
                
                if(count % 2){
                    valid = false;
                    break;    
                }
            }    
            if(!valid)
                break;
        }    
        if(valid){
            answer ++;
            answer = answer % 1000000000;    
        }
        return;
    }
    int x = box/m;
    int y = box%m;
    if(map[x][y] == '.'){
        map[x][y] = 'B';
        paint(box+1);
        map[x][y] = 'R';
        paint(box+1);   
        map[x][y] = '.'; 
    }else{
        paint(box + 1);    
    }
    return;
}

int main(){
    
    cin >> n >> m >> k;
    
    memset(map, '.', sizeof map);
    
    for(int i = 0; i < k; i++){
        int x, y, c;
        cin >> x >> y >> c;
        char color = c == 1 ? 'R' : 'B';
        map[x-1][y-1] = color;    
    }
    
    paint(0);   
    
    
    //print();
    cout << answer << endl;

    //system("pause");
    return 0;    
}