Liczba wyborów symetrycznych

Limit pamięci: 32 MB

Dane są dwa ciągi słów oraz , gdzie . Kolejno dla każdego od do wybieramy jedno z dwóch słów: albo i wybrane słowa składamy (kolejne wybrane słowo dopisujemy do poprzednich z prawej strony). Wybór składa się z decyzji, czy w kolejnym kroku wybrać odpowiedni -ty wyraz z pierwszego, czy z drugiego ciągu słów. Bardziej formalnie: wybór jest wyrazowym ciągiem liczb lub . Różne wybory mogą dać w wyniku to samo słowo. Wybór nazywamy symetrycznym, gdy jego wynikiem jest palindrom — tzn. takie słowo, które nie zmienia się, gdy je czytamy od strony prawej do lewej.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia liczbę i dwa -wyrazowe ciągi słów i ,
• oblicza liczbę wszystkich wyborów symetrycznych dla tych dwóch ciągów słów,
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia . W następnych wierszach są zapisane kolejne słowa ciągu — każde w osobnym wierszu. W następnych wierszach są zapisane — w taki sam sposób — kolejne słowa ciągu . Wszystkie słowa składają się wyłącznie z małych liter alfabetu angielskiego od a do z i mają łączną długość nie mniejszą niż i nie większą niż .

Wyjście

Na standardowe wyjście należy zapisać jedną liczbę całkowitą nieujemną, a mianowicie liczbę wszystkich wyborów symetrycznych.

Przykład

Dla danych wejściowych:

5
ab
a
a
ab
a
a
baaaa
a
a
ba

poprawną odpowiedzią jest:

12

Autor zadania: Wojciech Rytter.