Cho xâu ~S~ và xâu ~T~.

~S~ gọi là xâu con của ~T~ nếu có thể thu được ~S~ từ ~T~ bằng cách xóa đi một số phần tử từ đầu và cuối ~T~ và giữ nguyên các phần tử còn lại.

Yêu cầu: Hãy đếm xem có bao nhiêu hoán vị phân biệt của ~S~ là xâu con của ~T~.

Input Format

• Dòng đầu tiên chứa xâu kí tự ~S~ (~|S|\le 2\times 10^5~) chỉ gồm các kí tự tiếng anh in thường

• Dòng đầu tiên chứa xâu kí tự ~T~ (~|T|\le 2\times 10^5~) chỉ gồm các kí tự tiếng anh in thường

Output Format

• Ghi ra số lượng xâu hoán vị phân biệt của ~S~ là xâu con của ~T~

Sample Input

aab 
abacabaa

Sample Output

2

Giải thích

Có hai hoán vị của aab là aba và aab là xâu con của abacabaa