Cho hai xâu ~S~ và ~T~, bạn hãy đếm số lần xuất hiện của hoán vị xâu ~T~ trong xâu ~S~.

Ví dụ:

• Với ~S =~ aabcaba và ~T =~ aab, ta có các hoán vị của ~T~ là các xâu aab, aba, baa. Như vậy, hoán vị của xâu ~T~ xuất hiện ~2~ lần trong xâu ~S~, tại vị trí ~0~ và ~4~ (đánh số từ ~0~).

• Với ~S =~ aaaaa và ~T =~ aa, có ~4~ lần xâu ~T~ xuất hiện trong xâu ~S~ tại các vị trí ~0, 1, 2~ và ~3~.

Dữ liệu

• Dòng đầu tiên gồm xâu ~S~ ~(1 \le |S| \le 10^6)~ chỉ chứa các chữ cái in thường (từ a đến z).

• Dòng thứ hai gồm xâu ~T~ ~(1 \le |T| \le |S|)~ chỉ chứa các chữ cái in thường (từ a đến z).

Kí hiệu ~|S|~ là độ dài của xâu ~S~.

Kết quả

In ra một số nguyên duy nhất là số lần các hoán vị của ~T~ xuất hiện trong ~S~ (số vị trí bắt đầu ~i~ mà xâu con độ dài ~|T|~ bắt đầu tại ~i~ là một hoán vị của ~T~).

Ví dụ

Sample Input 1

aabcaba
aab

Sample Output 1

2

Sample Input 2

aaaaa
aa

Sample Output 2

4

Sample Input 3

vkxjzvdkzjxvkabcd
vkxjz

Sample Output 3

4

Chấm điểm

• Subtask 1 (~10\%~ số test): ~|T| = 1~

• Subtask 2 (~10\%~ số test): ~|S| \le 3000~, và tất cả các ký tự trong ~T~ đều bằng nhau

• Subtask 3 (~20\%~ số test): Tất cả các ký tự trong ~T~ đều bằng nhau

• Subtask 4 (~60\%~ số test): Không có ràng buộc gì thêm.