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ừ chỉ số nhỏ đến chỉ số lớn của các kí tự, Bob sẽ lần lượt chọn đúng $k$ xâu con khác rỗng (xâu con gồm các kí tự kề nhau) của xâu A và không giao nhau. Sau đó 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?

Bạn hãy lập trình để tìm kết quả giúp Bob nhé.

Dữ liệu cho trong tệp 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 là: độ dài xâu A; độ dài xâu B và số xâu con cần chọn.
• Dòng thứ hai gồm một xâu độ dài $n$ là xâu A.
• Dòng thứ ba gồm một xâu độ dài $m$ là xâu B.

Kết quả ghi ra tệp văn bản CHONXAU.OUT gồm một số nguyên là giá trị khi lấy số lượng cách chọn chia lấy dư cho $10^9 + 7$.

• Có 25% số test ứng với $k = 1$, $1 \le n \le 1000$, $1 \le m \le 100$, $1 \le k \le m \le n$;
• Có 25% số test ứng với $k = 2$, $1 \le n \le 1000$, $1 \le m \le 100$, $1 \le k \le m \le n$;
• Có 25% số test ứng với $k \ge 3$, $1 \le n \le 1000$, $1 \le m \le 100$, $1 \le k \le m \le n$;
• Có 25% số test còn lại ứng với $k \ge 3$, $1000 < n \le 100000$, $1 \le m \le 20$, $1 \le k \le m \le n$.