Để phục vụ cho nhu cầu học tập của các bé tiểu học vừa bước vào năm học mới, thầy Trường đã chế tạo ra một chiếc máy hỗ trợ đếm từ, cơ chế hoạt động của máy như sau: cho đầu vào là một xâu từ khóa \(K\) và một xâu kí tự \(X\). Máy sẽ đọc lần lượt các kí tự trong xâu \(X\) duy nhất một lần từ trái qua phải, ban đầu máy chỉ làm được những công việc đơn giản là nếu kí tự trong xâu \(X\) tồn tại trong từ khóa \(K\) máy sẽ dùng một bộ nhớ để lưu giữ từ đó và thực hiện phép đếm. Tuy nhiên để cho chiếc máy có thể thông minh hơn thầy Trường đã quyết định bổ sung thêm một chút mã lệnh, chiếc máy lúc này không những đếm được các từ trong xâu \(X\) xuất hiện trong từ khóa K mà còn có thể cho biết có bao nhiêu cách kết hợp các kí tự tìm kiếm được trong dãy \(X\) để tạo thành đầy đủ một từ khóa K hợp lệ, đảm bảo rằng các kí tự phải ghép thành đầy đủ một từ khóa \(K\) mặt khác các kí tự này không nhất thiết phải xuất hiện liên tiếp nhau trong xâu \(X\), nhưng cần xuất hiện theo đúng quy luật trước sau tương ứng với vị trí các kí tự đó trong xâu \(X\).

Bạn hãy viết chương trình để mô phỏng lại cách hoạt động của máy đếm từ này nhé!

Ví dụ: cho dãy kí tự như sau (để thuận tiện ta sẽ đánh các vị trí tương ứng của các kí tự ở hàng đầu tiên của bảng):

Nếu từ khóa là ab thì dãy sẽ có 2 trường hợp thỏa mãn( ký tự a ở vị trí thứ 2 ghép với kí tự b ở vị trí thứ 4 và kí tự b ở vị trí thứ 6 được bôi đen tạo thành 2 từ ab hợp lệ. Để dễ hiểu cách kết hợp các kí tự ở các vị trí là: 2-4, 2-6 tạo thành từ hợp lệ)

Nếu từ khóa là abc thì dãy đã cho sẽ có 4 trường hợp thỏa mãn, các kí tự sẽ ghép được với nhau ở chỉ số tương ứng: 2-4-8, 2-6-8, 2-4-10, 2-6-10.

Input

• Dòng đầu tiên là xâu từ khóa K có độ dài <=10 kí tự (Từ a-z, không chứa khoảng trắng, các kí tự phân biệt chỉ xuất hiện duy nhất một lần)

• Dòng tiếp theo là xâu cần kiểm tra \(X\) có độ dài \(\leq 1000\) kí tự (từ \(a-z\), không chứa khoảng trắng)

Output

• Một số nguyên là số các từ khóa \(K\) tìm được trong dãy \(X\) thỏa mãn yêu cầu.

Ví dụ:

Input 1

abc
ghbaakbnchbkc

Output 1

6

Input 2

a
aaaaaaa

Output 2

7

Input 3

abc
abcabc

Output 3

4

Input 4

abcd
xhdcapbmcqcbdlasddfcd

Output 4

10