#include<bits/stdc++.h>
using namespace std;
#define int long long
int MOD = 1000000009;
signed main()
{
int R, C, Q;
cin >> R >> C >> Q;
R--;
vector<vector<vector<int>>> options = {vector<vector<int>>(C, vector<int>(C, 0))};
vector<vector<int>> res(C, vector<int>(C, 0));
for (int i = 0; i < C; i++)
{
res[i][i] = 1;
}
for (int i = 0; i < C; i++)
{
options[0][i][i] = 1;
if (i > 0) options[0][i][i-1] = 1;
if (i < C-1) options[0][i][i+1] = 1;
}
int X = 1;
int x = 1;
if (R & X)
{
vector<vector<int>> res2(C, vector<int>(C, 0));
for (int i = 0; i < C; i++)
{
for (int j = 0; j < C; j++)
{
for (int k = 0; k < C; k++)
{
res2[i][j] += res[i][k] * options[options.size()-1][k][j];
res2[i][j] %= MOD;
}
}
}
res = res2;
}
while (X < R)
{
options.push_back(vector<vector<int>>(C, vector<int>(C, 0)));
for (int i = 0; i < C; i++)
{
for (int j = 0; j < C; j++)
{
for (int k = 0; k < C; k++)
{
options[options.size()-1][i][j] += options[options.size()-2][i][k] * options[options.size()-2][k][j];
options[options.size()-1][i][j] %= MOD;
}
}
}
X <<= 1;
x += 1;
if (R & X)
{
vector<vector<int>> res2(C, vector<int>(C, 0));
for (int i = 0; i < C; i++)
{
for (int j = 0; j < C; j++)
{
for (int k = 0; k < C; k++)
{
res2[i][j] += res[i][k] * options[options.size()-1][k][j];
res2[i][j] %= MOD;
}
}
}
res = res2;
}
}
vector<int> out = {};
for (int i = 0; i < Q; i++)
{
char k;
int c1, c2;
cin >> k >> c1 >> c2;
c1--; c2--;
out.push_back(res[c1][c2]);
}
for (int i = 0; i < Q; i++)
{
cout << R << " " << out[i] << endl;
}
// for (int i = 0; i < options.size(); i++)
// {
// for (int j = 0; j < options[0].size(); j++)
// {
// for (int k = 0; k < options[0][0].size(); k++)
// {
// cout << options[i][j][k] << " ";
// }
// cout << endl;
// }
// cout << endl;
// }
// for (int j = 0; j < res.size(); j++)
// {
// for (int k = 0; k < res[0].size(); k++)
// {
// cout << res[j][k] << " ";
// }
// cout << endl;
// }
}
