You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Một xâu $Z = z_1z_2…z_k$ được gọi là một xâu con của xâu $X = x_1x_2…x_m$ nếu có một dãy tăng thực sự $<i_1, i_2, … , i_k>$ sao cho với mọi $j = 1, 2, … , k$, ta có $x_{i_j} = z_j$.

Ví dụ: $Z$ = bcdb là một xâu con của xâu $X$ = abcbdab với tập chỉ số tương ứng $<2, 3, 5, 7>$.

Yêu cầu

Hãy đếm số lần xuất hiện xâu $Z$ trong xâu $X$.

Dữ liệu

Dòng đầu tiên là xâu $X$, bao gồm các chữ cái thường và có độ dài không quá 10000.

Dòng tiếp theo là xâu $Z$ cũng chỉ chứa các kí tự chữ cái thường và có độ dài không quá 100.

Kết quả

Ghi ra số lần xuất hiện của xâu con $Z$ trong xâu $X$ đếm được.

Hạn chế: Dữ liệu vào đảm bảo số lần xuất hiện của xâu con Z trong xâu X không lớn hơn $10^{18}$.

Ví dụ

babgbag
bag

5

rabbbit
rabbit

3