Problem description

Gaderypoluki to prosty szyfr, często stosowany w harcerstwie. Klucz szyfrowania (niepusty, o parzystej długości, złożony z parami różnych liter) dzieli się na pary sąsiednich znaków. Dla każdego analizowanego znaku z tekstu jawnego poszukiwany jest on w kluczu. W przypadku znalezienia, jest on zamieniany na drugi znak z pary w kluczu. Jeśli jednak znak tekstu nie występuje w kluczu, pozostawiany jest bez zmian.

Dla przykładu: jeśli kluczem szyfrowania jest GADERYPOLUKI, a szyfrowany tekst to BIEGNAORIENTACJE, wówczas zaszyfrowany tekst będzie wyglądał tak: BKDANGPYKDNTGCJD.

Jasio, który ostatnio został harcerzem, zapomniał klucza szyfrowania. Szczęśliwie jednak, pamięta on ostatnio szyfrowaną wiadomość zarówno jako tekst jawny oraz tekst tajny po zaszyfrowaniu. Chciałby na tej podstawie odtworzyć klucz szyfrowania, w razie gdyby później okazał się znowu potrzebny. Niestety, jako kolega Jasia zauważasz w jego pomyśle pewien problem.

Napisz program, który: wczyta tekst jawny oraz tekst tajny zaszyfrowany szyfrem gaderypoluki, wyznaczy liczbę kluczy szyfrowania i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się niepusty ciąg wielkich liter alfabetu angielskiego – tekst jawny zapamiętany przez Jasia. W drugim wierszu wejścia znajduje się niepusty ciąg wielkich liter alfabetu angielskiego – tekst tajny zapamiętany przez Jasia.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – reszta z dzielenia przez 10⁹ + 7 liczby kluczy szyfrowania, które mogły prowadzić do uzyskania tekstu tajnego po zaszyfrowaniu tekstu jawnego.

Uwaga

Jasio mógł się pomylić, więc wynik może być równy 0.

Ograniczenia

Długość każdego z tekstów na wejściu nie przekracza 100 000 znaków.

Przykład

BIEGNAORIENTACJE
BKDANGPYKDNTGCJD

751595221