#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
while(T--){
int n,m;
int x,y;
int k;
long long arr[55][55] = {0};
int block[55][2];
/// for home to Ani's home
for(int i=0; i<k; i++){
int tx,ty;
arr[tx][ty] = -1;
block[i][0] = tx;
block[i][1] = ty;
}
arr[1][1] = 1;
for(int i=2; i<=50; i++){
if(arr[1][i] == -1) arr[1][i] = 0;
else arr[1][i] = arr[1][i-1];
if(arr[i][1] == -1) arr[i][1] = 0;
else arr[i][1] = arr[i-1][1];
}
for(int i=2; i<=51; i++){
for(int j=2; j<51; j++){
if(arr[i][j] == -1) arr[i][j] = 0;
else arr[i][j] = arr[i-1][j] + arr[i][j-1] ;
arr[i][j]%=10004;
}
}
/// ans = the ways from home to Ani's home
long long ans = arr[x][y];
for(int i=1; i<=52; i++){
for(int j=1; j<52; j++){
arr[i][j] = 0;
}
}
for(int i=0; i<k; i++){
arr[block[i][0]][block[i][1]] = -1;
}
arr[x][y] = 1;
for(int i=y+1; i<=50; i++){
if(arr[x][i] == -1) arr[x][i] = 0;
else arr[x][i] = arr[x][i-1];
}
for(int i=x+1; i<=50; i++){
if(arr[i][y] == -1) arr[i][y] = 0;
else arr[i][y] = arr[i-1][y];
}
for(int i=x+1; i<=51; i++){
for(int j=y+1; j<51; j++){
if(arr[i][j] == -1) arr[i][j] = 0;
else arr[i][j] = arr[i-1][j] + arr[i][j-1] ;
arr[i][j]%=10004;
}
}
printf("%lld\n",(ans
*arr
[n
][m
])%10004); /// final result }
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkKewogICAgaW50IFQ7CiAgICBzY2FuZigiJWQiLCZUKTsKICAgIHdoaWxlKFQtLSl7CiAgICAgICAgaW50IG4sbTsKICAgICAgICBzY2FuZigiJWQlZCIsJm4sJm0pOwogICAgICAgIGludCB4LHk7CiAgICAgICAgc2NhbmYoIiVkJWQiLCZ4LCZ5KTsKCiAgICAgICAgaW50IGs7CiAgICAgICAgc2NhbmYoIiVkIiwmayk7CgogICAgICAgIGxvbmcgbG9uZyBhcnJbNTVdWzU1XSA9IHswfTsKICAgICAgICBpbnQgYmxvY2tbNTVdWzJdOwoKCiAgICAgICAgLy8vIGZvciBob21lIHRvIEFuaSdzIGhvbWUKICAgICAgICBmb3IoaW50IGk9MDsgaTxrOyBpKyspewogICAgICAgICAgICBpbnQgdHgsdHk7CiAgICAgICAgICAgIHNjYW5mKCIlZCVkIiwmdHgsJnR5KTsKICAgICAgICAgICAgYXJyW3R4XVt0eV0gID0gIC0xOwogICAgICAgICAgICBibG9ja1tpXVswXSA9IHR4OwogICAgICAgICAgICBibG9ja1tpXVsxXSA9IHR5OwogICAgICAgIH0KCiAgICAgICAgYXJyWzFdWzFdID0gMTsKICAgICAgICBmb3IoaW50IGk9MjsgaTw9NTA7IGkrKyl7CiAgICAgICAgICAgIGlmKGFyclsxXVtpXSA9PSAtMSkgYXJyWzFdW2ldID0gMDsKICAgICAgICAgICAgZWxzZSBhcnJbMV1baV0gPSBhcnJbMV1baS0xXTsKCiAgICAgICAgICAgIGlmKGFycltpXVsxXSA9PSAtMSkgYXJyW2ldWzFdID0gMDsKICAgICAgICAgICAgZWxzZSBhcnJbaV1bMV0gPSBhcnJbaS0xXVsxXTsKCiAgICAgICAgfQoKICAgICAgICBmb3IoaW50IGk9MjsgaTw9NTE7IGkrKyl7CiAgICAgICAgICAgIGZvcihpbnQgaj0yOyBqPDUxOyBqKyspewogICAgICAgICAgICAgICAgaWYoYXJyW2ldW2pdID09IC0xKSBhcnJbaV1bal0gPSAwOwogICAgICAgICAgICAgICAgZWxzZSBhcnJbaV1bal0gPSBhcnJbaS0xXVtqXSAgKyBhcnJbaV1bai0xXSA7CgogICAgICAgICAgICAgICAgYXJyW2ldW2pdJT0xMDAwNDsKICAgICAgICAgICAgfQogICAgICAgIH0KCgoKICAgICAgICAvLy8gYW5zID0gdGhlIHdheXMgZnJvbSBob21lIHRvIEFuaSdzIGhvbWUKICAgICAgICBsb25nIGxvbmcgYW5zID0gYXJyW3hdW3ldOwoKICAgICAgICAgZm9yKGludCBpPTE7IGk8PTUyOyBpKyspewogICAgICAgICAgICBmb3IoaW50IGo9MTsgajw1MjsgaisrKXsKICAgICAgICAgICAgICAgIGFycltpXVtqXSA9IDA7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgZm9yKGludCBpPTA7IGk8azsgaSsrKXsKICAgICAgICAgICAgYXJyW2Jsb2NrW2ldWzBdXVtibG9ja1tpXVsxXV0gID0gIC0xOwogICAgICAgIH0KCiAgICAgICAgYXJyW3hdW3ldID0gMTsKICAgICAgICBmb3IoaW50IGk9eSsxOyBpPD01MDsgaSsrKXsKICAgICAgICAgICAgaWYoYXJyW3hdW2ldID09IC0xKSBhcnJbeF1baV0gPSAwOwogICAgICAgICAgICBlbHNlIGFyclt4XVtpXSA9IGFyclt4XVtpLTFdOwogICAgICAgIH0KICAgICAgICBmb3IoaW50IGk9eCsxOyBpPD01MDsgaSsrKXsKICAgICAgICAgICAgaWYoYXJyW2ldW3ldID09IC0xKSBhcnJbaV1beV0gPSAwOwogICAgICAgICAgICBlbHNlIGFycltpXVt5XSA9IGFycltpLTFdW3ldOwoKICAgICAgICB9CiAgICAgICAgZm9yKGludCBpPXgrMTsgaTw9NTE7IGkrKyl7CiAgICAgICAgICAgIGZvcihpbnQgaj15KzE7IGo8NTE7IGorKyl7CiAgICAgICAgICAgICAgICBpZihhcnJbaV1bal0gPT0gLTEpIGFycltpXVtqXSA9IDA7CiAgICAgICAgICAgICAgICBlbHNlIGFycltpXVtqXSA9IGFycltpLTFdW2pdICArIGFycltpXVtqLTFdIDsKICAgICAgICAgICAgICAgIGFycltpXVtqXSU9MTAwMDQ7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHByaW50ZigiJWxsZFxuIiwoYW5zKmFycltuXVttXSklMTAwMDQpOyAvLy8gZmluYWwgcmVzdWx0CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K