Chứng cứ đỏ

Vụ án xảy ra tại quán cà phê Poirot và Conan đã tìm thấy vật chứng quan trọng. Trên vật chứng có ghi hai dòng mật mã ~s~ độ dài ~n~ và ~t~ độ dài ~m~. Conan suy đoán rằng có đến hai hung thủ trong vụ án và phải giải quyết hai dòng mật mã này theo hai cách khác nhau:

• Cách ~1~: Đếm xem có bao nhiêu xâu con liên tiếp của ~s~ trùng với ~t~.
• Cách ~2~: Đếm xem có bao nhiêu xâu con không liên tiếp của ~s~ trùng với ~t~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n \le 10^5,1 \le m \le 100)~.
• Dòng thứ hai chứa mật mã ~s~ độ dài ~n~ chỉ gồm các ký tự bảng chữ cái in thường.
• Dòng thứ ba chứa mật mã ~t~ độ dài ~m~ chỉ gồm các ký tự bảng chữ cái in thường.
• Dòng cuối cùng chứa số nguyên ~k~ là cách giải quyết mật mã ~(1 \le k \le 2)~

Output

• Với mỗi cách giải quyết mật mã, in ra số lượng xâu con thỏa mãn. Kết quả chia lấy dư cho ~10^9 + 7~.

Samples

7 2
bacacca
ac
1

2

7 2
bacacca
ac
2

5

Scoring

• Subtask ~1~ với ~50\%~ số điểm: ~k=1~
• Subtask ~2~ với ~50\%~ số điểm: ~k=2~