Yêu cầu

Cho một chuỗi ký tự S có độ dài N. Một chuỗi vô hạn được tạo ra bằng cách lặp lại chuỗi S liên tiếp nhau.

Yêu cầu: Trong T ký tự đầu tiên của chuỗi vô hạn này, chữ cái K xuất hiện bao nhiêu lần?

Dữ liệu vào (File CHUOI.INP)

Dòng 1: Chuỗi S (độ dài không quá 10^5 ký tự, không chứa dấu cách).
Dòng 2: Số nguyên dương T (1 <= T <= 10^18).
Dòng 3: Ký tự K.

Đầu ra (File CHUOI.OUT)

Một số nguyên duy nhất là kết quả tìm được.

Ví dụ

Input:

abcac
10
a

Output:

4

Giải thích: Chuỗi vô hạn là "abcacabcac...". 10 ký tự đầu tiên là "abcacabcac". Chữ cái 'a' xuất hiện 4 lần.