Olympic Tin học Sinh Viên

   Với các nhà hóa học, bảng tuần hoàn là kim chỉ nam để tìm ra các nguyên tố mới. Với các nhà sinh học bản đồ gien là la bàn để tìm ra các mắt xích còn thiếu trong sơ đồ tiến hóa của sinh vật. Bộ Gien của một sinh vật hiện đại đặc trưng bởi xâu S chỉ chứa các ký tự la tinh thường.

    Mỗi ký tự tương ứng với một gien, các kí tự khác nhau tương ứng với các gien khác nhau. Sinh vật này là sản phẩm tiến hóa từ một sinh vật tổ tiên có bộ gien đặc trưng bởi xâu T cũng chỉ chứa các ký tự la tinh thường thể hiện các gien và trình tự liên kết các gien đó là trình tự xuất hiện các chữ cái trong xâu.

    Mỗi ký tự giống nhau trong S và T cùng chỉ tới một gien như nhau. Trong quá trình tiến hóa, gien của sinh vật, dưới sự tác động của môi trường có thể bị đột biến dẫn đến xuất hiện một số gien mới được chèn vào. Các gien mới này có thể chiếm vị trí ở trước, sau hoặc chèn giữa các gien cũ. Mỗi gien mới ở sinh vật hiện đại có thể giống hoặc khác các gien của sinh vật ban đầu.

    Về nguyên tắc trong bộ gien của sinh vật hiện đại phải có các gien như ở động vật tổ tiên với việc bảo lưu trình tự xuất hiện (nhưng không nhất thiết phải liên tiếp nhau như trước). Như vậy, nếu có sinh vật trung gian giữa sinh vật tổ tiên và sinh vật hiện đại thì gien của sinh vật này phải một mặt chứa các gien giống như của sinh vật tổ tiên kể cả trình tự xuất hiện, mặt khác gien này phải đóng vài trò cầu nối tiến hóa lên gien của sinh vật hiện đại theo quá trình đột biến đã nêu ở trên.

  Ví dụ:

      Nếu bộ gien của sinh vật hiện đại là ‘cabba’, còn bộ gien của sinh vật tổ tiên là ‘aba’ thì sinh vật trung gian sẽ có thể có bộ gien là ‘caba’ hoặc ‘abba’.

      Như vậy có hai loại sinh vật tiềm năng có thể là khâu trung gian trong quá trình tiến hóa. Hai loại sinh vật tiềm năng gọi là khác nhau, nếu chúng có xâu đặc trưng cho bộ gien khác nhau.

  Yêu cầu: Cho hai xâu S và T đặc trưng cho bộ gien của sinh vật hiện đại và sinh vật tổ tên, mỗi xâu có độ dài không quá 20. Gọi N là số loại sinh vật tiềm năng khác nhau có thể xuất hiện trong quá trình tiến hóa. Hãy tính giá trị N mod 107.

Input

- Dòng đầu tiên chứa xâu S,
- Dòng thứ 2 chứa xâu T.

Output

 Gồm 1 dòng chứa số N mod 10⁷

Example

Input:
cabba 
aba

Output:
2