Вася не так давно стал пользоваться Интернетом, поэтому пока у него есть только два почтовых ящика на двух разных серверах. Пароль для каждого из ящиков представляет собой непустую строку, состоящую из маленьких латинских букв. Известно, что оба почтовых сервера проверяют правильность пароля следующим образом: настоящий пароль должен быть подпоследовательностью введённой пользователем строки.

Васе трудно запомнить оба пароля, поэтому он хочет придумать один универсальный пароль, который гарантированно подошёл бы к обоим почтовым ящикам. Так как Вася не сможет запомнить слишком длинный пароль, то его интересуют только универсальные пароли минимальной длины. Теперь Васе стало интересно, сколько же таких паролей существует, и он обратился за помощью к вам.

В каждой из двух строк записан один из настоящих паролей для входа на почтовый сервер. Длина каждого из них не превосходит 2000 символов.

В единственной строке выведите количество универсальных паролей минимальной длины по модулю 10⁹ + 7.

Во втором примере подходят следующие пароли: abcaba, abcbab, acbcab, cabcab.