Trò chơi ô chữ được diễn ra trên bảng chữ hình chữ nhật kích thước m×n. Các dòng của bảng được đánh số từ 1 đến m, từ trên xuống dưới, các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i, j). Mỗi ô của lưới chứa một ký tự.

Khi bắt đầu trò chơi, người chơi sẽ được cho một từ khóa P là một xâu ký tự và nhiệm vụ của người chơi là xuất phát từ ô (1, 1), kết thúc tại ô (m, n) để tìm một đường đi trên bảng chữ chứa từ khoá P. Tại mỗi bước, người chơi có thể di chuyển sang ô kề cạnh bên phải hoặc sang ô kề cạnh bên dưới. Khi kết thúc trò chơi, người chơi nhận được một xâu ký tự T gồm các ký tự trong các ô trên đường đi được xếp liên tiếp nhau. Người chơi giành chiến thắng nếu từ khóa P xuất hiện trong xâu T, nghĩa là từ khoá P trùng với một đoạn gồm các ký tự liên tiếp trong T.

Yêu cầu: Cho bảng chữ và từ khóa P, đếm số lượng đường đi khác nhau giúp người chơi giành chiến thắng. Hai đường đi được gọi là khác nhau nếu tồn tại một ô thuộc đường đi này nhưng không thuộc đường đi kia.

Dữ liệu: Vào từ file văn bản WORDGAME.INP:

• Dòng đầu tiên ghi ba số nguyên dương m, n, D (D ≤ 10⁹, m,n <=100)
• Dòng thứ hai chứa từ khóa P là một xâu gồm không quá m+n-1 chữ cái in hoa, mỗi chữ cái được lấy trong 26 chữ cái từ ‘A’ đến ‘Z’.
• Tiếp đến là m dòng mô tả bảng chữ, mỗi dòng chứa một xâu gồm n ký tự, mỗi ký tự là một chữ cái in hoa trong 26 chữ cái từ ‘A’ đến ‘Z’.

Kết quả: Ghi ra file văn bản WORDGAME.OUT một số là số lượng đường đi đếm được chia dư cho D.

Ví dụ: