Để tìm kiếm tài nguyên khoáng sản, các nhà khoa học đã phát triển một loại máy quét đặc biệt.
Chúng ta biểu diễn khu vực tìm kiếm bằng một bảng gồm hàng và cột. Các hàng được đánh số từ đến từ trên xuống dưới, và các cột được đánh số từ đến từ trái sang phải. Trong mỗi ô có thể tồn tại tài nguyên khoáng sản.
Máy quét hoạt động như sau: nó có thể được khởi động tại cột thứ và trả về số lượng ô chứa khoáng sản trong khu vực quét. Khu vực quét bao gồm tất cả các ô ở cột , ô đầu tiên của cột , ô đầu tiên của cột , và cứ thế tiếp tục. Hình dưới đây minh họa các khu vực quét với các giá trị khác nhau khi và .
Minh họa các khu vực quét
Bây giờ, cho trước kết quả trả về của máy quét trên tất cả các cột, chúng ta dùng để biểu thị kết quả quét tại cột thứ . Nếu với một bảng nào đó, ta đã xác định mỗi ô có chứa khoáng sản hay không, và dựa vào bảng đó, kết quả trả về của máy quét khớp với các giá trị đã cho, thì bảng đó được gọi là hợp lệ. Ví dụ, nếu trong ví dụ trên, kết quả trả về của máy quét là , thì dưới đây là một bảng hợp lệ (các ô chứa khoáng sản được biểu thị bằng hình tam giác màu đen):
Hình minh họa cho ví dụ bên dưới
Dựa vào kết quả quét đã cho, hãy xác định số lượng bảng hợp lệ và in ra số lượng đó sau khi lấy modulo cho . Xin lưu ý, máy quét có thể bị lỗi, dẫn đến không có bảng nào hợp lệ, trong trường hợp này hãy in ra .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và (), lần lượt là số cột và số hàng.
Dòng thứ hai chứa số nguyên (), là kết quả trả về của máy quét tại mỗi cột.
Kết quả: In ra một số nguyên, là số lượng bảng hợp lệ sau khi lấy modulo cho .
Ví dụ:
Dữ liệu:
5 3
2 1 2 3 2
Kết quả:
24
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.
