Draco Malfoy 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 đố Harry có thể giải được. Bài toán được phát biểu như sau: “Cho 2 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~ để 2 xâu còn lại của mỗi xâu là giống nhau, không tính xâu rỗng. 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à chỉ một trong hai cách kí tự bị loại bỏ hoặc tồn tại một vị trí ~j~ của xâu ~p~ mà chỉ một trong hai cách kí tự này bị loại bỏ.”

Yêu cầu: Đếm số cách loại bỏ ký tự từ hai xâu ~s~ và ~p~ để thu được các xâu con chung giống nhau (không tính xâu rỗng), kết quả lấy dư cho ~10^9 + 7~.

Input

• 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’.

Output

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

Sample Input 1

abc
aaa

Sample Output 1

3