• Rùa 🐢 có một vài ý nghĩ về chuỗi con như sau:

Cho hai chuỗi ký tự \(s\) và \(t\). Gọi một chuỗi ký tự mới \(ss\) bằng \(K\) bản copy của chuỗi \(s\) gắn liền vào bên phải hoặc bên trái của nhau. Hãy đếm số lần xuất hiện chuỗi \(t\) trong chuỗi \(ss\).

• Định nghĩa của sự xuất hiện chuỗi:

Chuỗi \(A\) xuất hiện trong chuỗi \(B\) khi nếu xóa đi bên trái cùng và bên phải cùng xâu \(B\) một số lượng ký tự (có thể là \(0\)) thì các ký tự còn lại ở giữa chính là xâu \(A\).

• Ví dụ: Chuỗi efg xuất hiện trong chuỗi abcdefgh vì có thể xóa abc bên trái và h bên phải để thu được abc.

Input

• Dòng đầu tiên chứa chuỗi không rỗng \(s\). Độ dài không lớn hơn \(10^5\).
• Dòng thứ hai chứa chuỗi không rỗng \(t\). Độ dài không lớn hơn \(10^3\) và độ dài chuỗi \(s\).
• Dòng thứ ba chứa một số nguyên \(K\). \((1 \leq K \leq 10^9)\)

Output

In ra một số nguyên, là số lần xuất hiện xâu \(t\) trong xâu \(ss\), được tạo thành bởi \(K\) chuỗi \(s\) ghép thành.

Example

abab
ab
3

6

aaaa
a
2

8