Nguồn: Ôn HN tháng 11/2016, Thầy Nguyễn Đức Nghĩa, Ngày 3
Bờm mới sưu tầm được một bài toán trên lưới ô vuông sau đây: Cho lưới ô vuông kích thước trong đó trên mỗi ô có ghi một chữ cái và một xâu gồm đúng chữ cái. Bắt đầu từ ô ở góc trên bên trái cần di chuyển đến ô ở góc đưới bên phải, trong quá trình di chuyển, từ một ô chỉ được phép di chuyển sang ô kề cạnh ở bên phải hoặc ở phía dưới. Cần xác định xem có bao nhiêu cách di chuyển mà dãy các chữ cái trong các ô trên đường di chuyển tạo thành xâu cho trước.
Yêu cầu: Hãy xác định số lượng đường di chuyển thoả mãn các điều kiện đặt ra.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên - là kích thước lưới;
Mỗi dòng trong dòng tiếp theo chứa chữ cái trong bảng chữ cái latin mô tả báng chữ cái. Các chữ cái ghi liên tục không có dấu cách.
Dòng cuối chứa xâu độ dài ký tự.
Dữ liệu ra:
Ghi ra một số nguyên là số lượng cách di chuyển thoả mãn các điều kiện đặt ra. Nếu , hãy ghi phân dư của phép chia cho .
Vị dụ:
Dữ liệu vào:
3
loc
ogo
gos
logos
Dữ liệu ra:
5
Giải thích:
Có cách di chuyển tạo thành xâu logos như hình sau:
