Một nhóm học sinh tiểu học đến một thành phố mới để tham quan và quyết định ghé thăm các di tích lịch sử ở đây. Chúng ta có thể coi thành phố này là một lưới hình chữ nhật kích thước , trong đó một số ô có các điểm tham quan.
Các bạn nhỏ bắt đầu hành trình từ ô , muốn đến ô , và sau đó quay trở lại điểm xuất phát. Ngoài ra, trong thành phố có điểm tham quan, nằm ở các ô , và họ phải ghé thăm tất cả các điểm này.
Hình minh họa
Họ có thể mất một phút để di chuyển từ ô đến một ô kề cạnh , nếu chúng kề nhau về cạnh, tức là thỏa mãn . Rõ ràng, để hoàn thành toàn bộ tuyến đường cần ít nhất phút, và chúng ta chỉ xem xét các tuyến đường có độ dài đúng bằng khoảng thời gian này.
Một tuyến đường được gọi là tuyến đường thú vị nếu thỏa mãn các điều kiện sau:
Họ mất đúng phút để hoàn thành tuyến đường;
Mỗi ô trên tuyến đường được đi qua nhiều nhất một lần;
Tuyến đường phải đi qua tất cả các ô chứa điểm tham quan.
Hãy giúp các bạn học sinh tính xem có tổng cộng bao nhiêu tuyến đường thú vị khác nhau. Vì kết quả có thể rất lớn, hãy in ra kết quả sau khi lấy mô-đun cho .
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên , và .
Trong dòng tiếp theo, mỗi dòng chứa hai số nguyên , cho biết vị trí của điểm tham quan thứ . Đảm bảo rằng tất cả các cặp là khác nhau.
Kết quả: In ra một số nguyên duy nhất là số lượng tuyến đường thú vị, lấy mô-đun cho .
Ví dụ:
Dữ liệu:
3 4 2
2 2
2 3
Kết quả:
6
Giải thích:
Hình giải thích các tuyến đường
Dữ liệu:
3 4 3
3 1
2 3
1 4
Kết quả:
0
Giới hạn:
Subtask #1: số điểm có ;
Subtask #2: số điểm khác có ; ;
Subtask #3: số điểm khác có ; ;
Subtask #4: số điểm còn lại không có ràng buộc bổ sung.
