Ta gọi xâu \(R\) là xâu con của xâu \(S\) nếu ta có thể thu được xâu \(R\) bằng cách xóa đi một vài ký tự của xâu \(S\) và giữ nguyên thứ tự các ký tự còn lại.

Xâu ký tự \(C\) được gọi là xâu con chung của hai xâu \(A\) và \(B\) nếu \(C\) là xâu con của \(A\) và \(C\) là xâu con của \(B\). Trong bài tập này nhiệm vụ của bạn cần tìm số lượng xâu con chung của hai xâu \(A\) và \(B\)

Dữ liệu vào

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

Dữ liệu ra

• In ra một đáp án duy nhất là số lượng xâu con chung của hai xâu. Vì đáp án có thể rất lớn nên hãy in ra đáp án khi lấy dư cho \(10^9+7\)

Input 1

abc
ab

Output 1

3

Giải thích

• Có ba xâu con chung là \(a,b,ab\)