#1235. CPATH

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: