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.

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.

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.

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~.

Scoring

Sample Input 1

abc
aaa

Sample Output 1

3