Trò chơi ô chữ

Nhân dịp kỷ niệm 15 năm thành lập VNG, nhận thấy đa số người tham gia đều là các lập trình viên xuất sắc, ban tổ chức đã sáng tạo ra trò chơi đố chữ như sau:

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

Khi trò chơi bắt đầu, người chơi được cho một từ khóa $P$ (là một xâu ký tự). 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)$ và tìm một đường đi trên bảng sao cho đường đi đó chứa từ khóa $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 ô 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ự được tạo thành bằng cách ghép nối lần lượt các ký tự trên các ô thuộc đường đi. Người chơi giành chiến thắng nếu từ khóa $P$ xuất hiện trong xâu ký tự thu được, nghĩa là $P$ khớp với một xâu con liên tiếp của xâu đó.

Ban tổ chức muốn biết có bao nhiêu đường đi khác nhau có thể giúp người chơi giành chiến thắng. Hãy giúp ban tổ chức tính toán nhé!

Yêu cầu: Cho bảng chữ nhật kích thước $m \times n$ và từ khóa $P$, hãy đế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 coi là khác nhau nếu tồn tại ít nhất một ô thuộc đường đi này nhưng không thuộc đường đi kia. Vì số lượng đường đi có thể rất lớn, kết quả cần được lấy phần dư cho $10^9+7$.

Đầu vào:

• Dòng đầu tiên chứa hai số nguyên dương $m, n$ ($1 \leq m, n \leq 100$);
• Dòng thứ hai chứa từ khóa $P$, là một xâu gồm từ $1$ đến $m+n-1$ chữ cái in hoa trong bảng chữ cái tiếng Anh từ 'A' đến 'Z';
• $m$ dòng tiếp theo mô tả bảng chữ, mỗi dòng chứa một xâu gồm $n$ chữ cái in hoa từ 'A' đến 'Z'.

Đầu ra: In ra một số nguyên duy nhất là số lượng đường đi đếm được theo modulo $10^9+7$.

Subtask (tham khảo):

• 50% số test có $m, n \leq 10$.
• 50% số test còn lại có $m, n \leq 100$.

Ví dụ 1:

Đầu vào:

3 3
VNG
VNG
VVV
GNG

Đầu ra:

3