Nhân dịp đang rảnh rỗi vì nghỉ học, Ami tặng LN một con số rất lớn. Nhưng LN rất chảnh nên chỉ thèm nhận 1 đoạn con liên tiếp của con số đó thôi. Chẳng hạn Ami tặng LN số 17092001 thì LN có thể nhận các số như 70, 2001, 1709, 00, ... Ami rất muốn con số mà LN nhận được chia hết cho p (con số tình yêu của họ). Vì vậy Ami nhờ các bạn đếm xem, có bao nhiêu đoạn con LN có thể chọn mà chia hết cho p.

Hai đoạn con khác nhau nếu chúng ở vị trí khác nhau trong con số của Ami. Đồng thời LN vẫn có thể chọn một đoạn con bắt đầu bằng 0.

Input:

Dòng đầu chứa số nguyên n (0 <= n < 10^1000000), con số mà Ami tặng LN. Lưu ý, vì Ami khá gà nên con số này có thể bắt đầu bởi số 0.

Dòng thứ hai chứa một số nguyên dương p (1 <= p <= 1000000), con số tình yêu của họ.

Trong subtask này, p là lũy thừa của một số nguyên tố, hay p = q^k với q là một số nguyên tố và k là một số nguyên dương.

Output:

In ra một số nguyên là số xâu con chia hết cho p.