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 109 + 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
| Wejście | Wyjście | |
|
|