Cho xâu M không quá 127 ký tự lấy từ tập F = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} và không bắt đầu bằng ký tự 0. Gọi S là xâu với giá trị ban đầu là xâu M.

Người ta biến đổi M theo quy tắc sau: đếm số lần xuất hiện các ký tự 0, 1, 2, ..., F, gọi K, là số lần xuất hiện ký tự i (với i lân lượt là 0, 1, 2, ... F). Với các Ki # 0 người ta viết liên tiếp xâu biểu diễn sô K; trong cơ số 16 và ký tự i. Xâu kết quả thu được là giá trị mới của M. Sau mỗi lần biến đổi người ta lại viết tiếp M vào sau S.

Ví dụ, với M = '150A', S nhận giá trị ban đầu là '150A'. Sau lần biến đổi thứ nhất ta có M là '1011151A' và S =150A1011151A'. Sau lần biến đổi thứ 2 ta có M là '1051151A' và S =150A1011151A1051151A'. Sau lần biến đổi thứ 3 ta có M là '1041251A' và S = '150A1011151A1051151A1041251A'.

Yêu cầu: Cho xâu M, số lần biến đổi L (0 ≤ L ≤ 10^7) và X là một ký tự từ tập F . Hãy đếm số lần xuất hiện X trong S thu được sau L lần biến đổi M.

Dữ liệu: Vào từ file văn bản DIGIT.INP:

Dòng thứ nhất chứa xâu M

Dòng thứ hai chứa số nguyên L

Dòng thứ bai chứa ký tự X

Kết quả: Đưa ra file văn bản DIGIT.OUT một số nguyên - số lần xuất hiện X.

Input:

150A
3
2

Output:

1