Chèn ký tự tăng LCS

Cho hai xâu \(A\) và \(B\) gồm các chữ cái thường. Gọi \(L\) là độ dài xâu con chung dài nhất của \(A\) và \(B\).

Ta muốn chèn đúng một chữ cái thường vào một vị trí nào đó của \(A\) (đầu xâu, cuối xâu hoặc giữa hai ký tự liên tiếp; xâu \(A\) có \(|A| + 1\) vị trí chèn) sao cho độ dài xâu con chung dài nhất của xâu mới và \(B\) trở thành \(L + 1\).

Hãy đếm số cặp (vị trí chèn, chữ cái được chèn) thoả mãn. Hai cặp có vị trí khác nhau luôn được tính là hai cách khác nhau, kể cả khi xâu thu được giống nhau.

Input

• Dòng thứ nhất chứa xâu \(A\).
• Dòng thứ hai chứa xâu \(B\).

Output

In ra một số nguyên là số cách chèn thoả mãn.

Constraints

• \(1 \le |A|, |B| \le 1010\)
• Hai xâu chỉ gồm chữ cái tiếng Anh viết thường.

Sample Input

abc
cbad

Sample Output

9

Explanation

Xâu con chung dài nhất của abc và cbad có độ dài \(1\). Có \(9\) cách chèn để độ dài này tăng lên \(2\), chẳng hạn chèn d vào cuối abc được abcd (có xâu con chung ad), hoặc chèn b vào đầu abc được babc (có xâu con chung ba).