Xâu con chung

Nhật rất hứng thú với các bài toán về xâu. Một hôm anh ta nghĩ ra một bài toán và thách đố Quang có thể giải được. Bài toán được phát biểu như sau:

Cho hai xâu $s$ và $p$, hãy đếm số cách khác nhau loại bỏ một số ký tự (hoặc không) ở xâu $s$ và xâu $p$ để hai xâu còn lại là giống nhau, không tính xâu rỗng. Các ký tự còn lại của mỗi xâu giữ nguyên thứ tự ban đầu (không nhất thiết liền nhau).

Hai cách được coi là khác nhau nếu tồn tại một vị trí $i$ của xâu $s$ mà ký tự tại đó chỉ bị loại bỏ trong một trong hai cách, hoặc tồn tại một vị trí $j$ của xâu $p$ mà ký tự tại đó chỉ bị loại bỏ trong một trong hai cách.

Dữ liệu vào

• Dòng đầu tiên chứa xâu $s$ chỉ gồm các ký tự từ 'a' đến 'z'.
• Dòng thứ hai chứa xâu $p$ chỉ gồm các ký tự từ 'a' đến 'z'.

Dữ liệu ra

Một dòng duy nhất là kết quả của bài toán lấy dư cho ${10}^9+7$.

Ràng buộc

• $1\le |s|,|p|\le 2000$.
• Hai xâu chỉ gồm các chữ cái Latin thường từ 'a' đến 'z'.

Subtasks

• Subtask 1 ($40\%$ số test): $|s|+|p|\le 20$.
• Subtask 2 ($60\%$ số test): $|s|\le 2000$, $|p|\le 2000$.

Ví dụ