Thiết kế mê cung

Alice mới tạo một trò chơi máy tính tìm đường trong mê cung, công việc tiếp theo cần thiết kế mê cung. Mê cung có kích thước \(m \times n\) ô, các hàng được đánh số từ 1 đến \(m\) từ trên xuống dưới và các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm ở hàng \(i\ (1 \leq i \leq m)\), cột \(j\ (1 \leq j \leq n)\) được gọi là ô \((i, j)\). Với mỗi ô có thể có tường ở các hướng Bắc, Đông, Nam, Tây. Có \(s\) ô bị cấm, bốn hướng xung quanh các ô cấm đều có tường, các ô còn lại gọi là ô tự do. Một vùng gồm các ô tự do mà hai ô đều có thể đi được tới nhau thông qua các ô tự do chung cạnh. Alice cần thiết kế mê cung thỏa mãn ba tính chất sau:

• \(1\)) Các ô ở biên phía Bắc (các ô ở hàng \(1\)) luôn có tường ở hướng Bắc; Các ô ở biên phía Đông (các ô ở cột \(n\)) luôn có tường ở hướng Đông; Các ô ở biên phía Nam (các ô ở hàng \(m\)) luôn có tường ở hướng Nam; Các ô ở biên phía Tây (các ô ở cột \(1\)) luôn có tường ở hướng Tây.
• \(2\)) Mỗi ô tự do đều phải có tường ở hướng Đông hoặc có tường hướng Nam hoặc có cả tường ở hướng Đông và hướng Nam.
• \(3\)) Số vùng trong mê cung bằng đúng \(k\).

Ví dụ, Alice cần thiết kế mê cung kích thước \(2 \times 3\) có hai ô cấm \((1,1),(2,1)\) và mê cung có đúng \(2\) vùng.

\begincenter

Một thiết kế thỏa mãn
\endcenter

\begincenter

Một thiết kế không thỏa mãn vì ô \((1,2)\) không thỏa mãn tính chất thứ hai
\endcenter

Yêu cầu: Cho \(m, n, k\) và \(s\) ô cấm, hãy đếm số mê cung khác nhau mà Alice có thể thiết kế được. Hai mê cung được gọi là khác nhau nếu có một bức tường trong mê cung này có còn trong mê cung kia không có.

Input

• Dòng đầu chứa các số nguyên \(m, n, k, s\ (0<k \leq m \times n; 0 \leq s<m \times n)\).
• Dòng thứ \(p\ (1 \leq p \leq s)\) trong \(s\) dòng tiếp theo chứa hai số nguyên \(i_{p}\) và \(j_{p}\ (1 \leq i_{p} \leq m; 1 \leq j_{p} \leq n\)) cho biết phòng bị cấm.

Output

• Gồm một dòng chứa một số nguyên là số mê cung có thể thiết kế được, vì kết quả có thể rất lớn nên chỉ cần đưa ra phần dư khi chia cho \(111539786\).

Example

2 3 2 2
1 1
2 1

5

Scoring

• Có \(30 \%\) số test có \(m \leq 5 ; n \leq 3\).
• Có \(20 \%\) số test khác có \(m \leq 100 ; n=3\) và các ô ở cột \(1\) và cột \(2\) đều là ô cấm.
• Có \(20 \%\) số test khác có \(m \leq 100 ; n=3\) và các ô ở cột \(1\) đều là ô cấm.
• Có \(20 \%\) số test khác có \(m \leq 100 ; n=3\).
• Có \(10 \%\) số test còn lại có \(m \leq 100 ; n \leq 10\).