Xét một bàn cờ vua có kích thước \(m \times n\) gồm có \(m\) dòng, \(n\) cột. Các dòng được đánh số từ 1 đến \(m\), các cột được đánh số từ 1 đến \(n\). Một số nằm trên dòng \(x\), cột \(y\) được ký hiệu là \((x,y)\). Một quân mã xuất phát từ một ô trên ban cờ có thể đi đến một trong bốn ô như hình vẽ.

Ngoài ra, trên bàn cờ có \(k\) ô mà quân mã không được phép đi vào. Những ô này gọi là ô bị cấm.

Yêu cầu: Tìm số cách di chuyển của quân mã từ ô \((x,y)\) cho trước đến ô \(m,n)\).

Dữ liệu vào:

+ Dòng đầu tiên ghi 4 số nguyên \(m,n,k\) và \(q\ (1 \leq m,n \leq 1000;0 \leq k \leq 10;1 \leq 10^{5})\)

+ Trên \(k\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên \(k_{x_{i}},\ k_{y_{i}}\ \)cho biết ô \((k_{x_{i}},\ k_{y_{i}})\) bị cấm \((1 \leq k_{x_{i}} < m;1 \leq k_{y_{i}} < n)\);

+ Trên \(q\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên \(x_{i},\ y_{i}\ (1 \leq x_{i} < m;1 \leq y_{i} < n)\)

Kết quả: Gồm \(q\) số nguyên \(w_{i}\), mỗi số trên một dòng cho biết số cách di chuyển quân mã từ ô \((x_{i},\ y_{i})\) cho trước đến ô \((m,n)\), trong đó \(w_{i}\) là phần dư của phép chia số cách quân mã di chuyển từ ô \(\left( x_{i},y_{i} \right)\) cho trước đến ô \((m,n)\) cho \(10^{9}\)

Ví dụ:

Ràng buộc:

+ Có 30% số test tương ứng 30% số điểm có \(1 \leq m,n \leq 100;k = 0;q \leq 10^{2}\);

+ Có 20% số test khác tương ứng 20% số điểm có \(1 \leq m,n \leq 100;0 < k \leq 10;q \leq 10^{2}\);

+ Có 50% số test còn lại tương ứng 50% số điểm không có ràng buộc gì thêm.