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é.

Input

• 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~.

Output

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~.

Scoring

Sample Input 1

6 3 1
aabaab
aab

Sample Output 1

2

Sample Input 2

6 3 2
aabaab
aab

Sample Output 2

7

Notes

Trong ví dụ thứ nhất, ~k=1~, có ~2~ cách chọn:

• ~\rightarrow~ (aab)aab

• ~\rightarrow~ aab(aab)

Trong ví dụ thứ hai, ~k=2~, có ~7~ cách chọn:

• ~\rightarrow~ (a)(ab)aab

• ~\rightarrow~ (a)aba(ab)

• ~\rightarrow~ a(a)ba(ab)

• ~\rightarrow~ (aa)(b)aab

• ~\rightarrow~ (aa)baa(b)

• ~\rightarrow~ aab(a)(ab)

• ~\rightarrow~ aab(aa)(b)