Câu 4. (4.0 điểm) Chọn xâu con

Bob có hai xâu ký tự \(A\) và \(B\) gồm các chữ cái latin thường. Theo hướng từ trái sang phải, Bob muốn chọn ra \(k\) xâu con rời nhau của \(A\). Xâu con được xác định là một đoạn liên tiếp trong \(A\). Bob sẽ lần lượt cộng dồn \(k\) xâu con đó (xâu con được lấy thứ tự chọn) để tạo thành xâu mới. Các xâu con không giao nhau. Số phép ghép những xâu này theo thứ tự được chọn để tạo thành một xâu mới.

Bob muốn biết có bao nhiêu cách chọn như vậy để xâu mới nhận được bằng xâu \(B\)?

Input

File văn bản CHONXAU.INP gồm:

• Dòng thứ nhất gồm ba số nguyên dương \(n, m, k\) lần lượt: độ dài xâu \(A\); độ dài xâu \(B\) và số lượng xâu con cần chọn.
• Dòng thứ hai ghi xâu ký tự độ dài \(n\) là xâu \(A\).
• Dòng thứ ba ghi xâu ký tự độ dài \(m\) là xâu \(B\).

Output

Kết quả:
Ghi ra tệp văn bản CHONXAU.OUT một số nguyên duy nhất là giá trị \(k\) lý số lượng cách chọn xâu con modulo \(10^9 + 7\).

Example

6 3 1
aabaab
aab

2

6 3 2
aabaab
aab

7