Từ lâu vương quốc đã có lòng tham, muốn chiếm trọn vương quốc làm lãnh thổ của mình. Nay nhờ có lãnh chúa mà ý đồ của vương quốc sắp trở thành hiện thực!
Vương quốc , giống như mọi vương quốc khác, có hình dạng là một khu vực hình chữ nhật. Ta có thể chia vương quốc thành hàng và cột, mỗi ô sẽ tượng trưng cho một tỉnh của vương quốc.
Lãnh chúa đã cho quân bí mật xâm chiếm tỉnh quan trọng của vương quốc . Việc chiếm trọn cả vương quốc giờ chỉ còn là lần lượt chiếm đóng nốt các tỉnh còn lại. Dở chứng kiêu ngạo, Lãnh chúa muốn thị uy quyền lực ra thế giới, yêu cầu các quan của mình tìm một cách lần lượt chiếm đóng các tỉnh còn lại sao cho số lần tất cả các tỉnh được chiếm tạo thành hình chữ nhật là nhiều nhất có thể. Đơn giản vì khi đó, các tỉnh đã chiếm sẽ có hình dạng của một vương quốc!
Các quan lóng ngóng mãi mới tìm ra một phương án cho Lãnh chúa của mình, trong khi Lãnh chúa, với khả năng toán học siêu cấp, đã tính ra số cách để chọn thỏa mãn yêu cầu bản thân. Còn bạn thì sao?
Dữ liệu vào:
Dòng đầu tiên gồm hai số và là số hàng và cột của vương quốc .
Dòng tiếp theo gồm số là số lượng các tỉnh đã chiếm đóng.
dòng tiếp theo, mỗi dòng gồm số và – thể hiện vị trí một tỉnh đã chiếm đóng. Dữ liệu đảm bảo tỉnh đôi một khác nhau.
Dữ liệu ra:
Một dòng duy nhất ghi số cách chọn lần lượt các tỉnh để chiếm đóng thỏa mãn yêu cầu của Lãnh chúa. Vì số này rất lớn, bạn chỉ cần in ra phần dư của nó khi chia cho .
