Đề bài

Bob có hai xâu kí tự \(A\) và \(B\) gồm các chữ cái latin thường.
Theo thứ tự từ chỉ số nhỏ đến chỉ số lớn của các kí tự trong \(A\), Bob sẽ chọn đúng \(k\) xâu con khác rỗng, các xâu con này không được giao nhau, và mỗi xâu con là một đoạn liên tiếp của \(A\).

Bob ghép các xâu con này theo thứ tự được chọn để tạo thành một xâu mới.
Hãy đếm xem có bao nhiêu cách chọn để xâu mới thu được bằng đúng xâu \(B\).

Kết quả cần được lấy modulo \(10^9 + 7\).

Dữ liệu vào

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

Dữ liệu ra

• Một số nguyên — số lượng cách chọn \(k\) xâu con sao cho ghép lại đúng xâu \(B\), lấy modulo \(10^9+7\).

Ràng buộc

• \(1 \le k \le m \le n\)
• \(1 \le n \le 1000\), \(1 \le m \le 100\), \(k = 1\) — 25% số test.
• \(1 \le n \le 1000\), \(1 \le m \le 100\), \(k = 2\) — 25% số test.
• \(1 \le n \le 1000\), \(1 \le m \le 100\), \(k \ge 3\) — 25% số test.
• \(1000 < n \le 100000\), \(1 \le m \le 20\), \(k \ge 3\) — 25% số test.

Sample Input 1

6 3 1
aabaab
aab

Sample Output 1

2

Sample Input 2

6 3 2
aabaab
aab

Sample Output 2

7

Giải thích

Sample 1 – \(k=1\)
Các cách chọn 1 đoạn liên tiếp của \(A\) sao cho bằng “aab” là:

• \((\text{aab})\)aab
• aab\((\text{aab})\)

Tổng cộng có 2 cách.

Sample 2 – \(k=2\)
Cần tách xâu \(B = \text{aab}\) thành 2 đoạn liên tiếp và khớp mỗi đoạn với một xâu con rời rạc của \(A\).

Các cách hợp lệ gồm:

• \((\text{a})(\text{ab})\): chọn ở các vị trí
  \((a)(ab)\)aab, \((a)\)aba\((ab)\), a\((a)\)ba\((ab)\), aab\((a)(ab)\)
• \((\text{aa})(\text{b})\):
  \((aa)(b)\)aab, \((aa)\)baa\((b)\), aab\((aa)(b)\)

Tổng cộng có 7 cách.