Równanie na słowach

Limit pamięci: 32 MB

Słowem dwójkowym nazywamy każdy niepusty ciąg złożony z lub . Równanie na słowach ma postać , gdzie i są cyframi dwójkowymi ( lub ) lub zmiennymi, to jest małymi literami alfabetu angielskiego. Dla każdej zmiennej jest ustalona długość słów dwójkowych, które można podstawiać w jej miejsce. Długość tę nazywamy długością zmiennej. Rozwiązanie równania na słowach polega na przypisaniu każdej zmiennej słowa dwójkowego o odpowiadającej tej zmiennej długości, w taki sposób, by po zastąpieniu zmiennych w równaniu przez przypisane im słowa, obie strony równania (słowa dwójkowe) były takie same.

Dla danego równania na słowach policz ile jest różnych rozwiązań tego równania.

Przykład

Niech będą długościami zmiennych w poniższym równaniu: To równanie ma różnych rozwiązań.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia liczbę równań i ich opisy;
• znajduję liczbę rozwiązań każdego równania;
• zapisuje wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita , . Jest to liczba równań. Następne wiersze zawierają opisy równań. Na każdy opis składa się wierszy. Między kolejnymi opisami nie ma pustych wierszy. Każde równanie jest opisane w następujący sposób:

W pierwszym wierszu opisu znajduje się liczba całkowita , . Jest to liczba różnych zmiennych w równaniu. Przyjmujemy, że zawsze zmiennymi jest pierwszych małych liter alfabetu angielskiego. W drugim wierszu jest zapisany ciąg liczb całkowitych dodatnich oddzielonych pojedynczymi odstępami. Te liczby to długości kolejnych zmiennych występujących w równaniu.

Trzeci wiersz opisu zawiera tylko jedną dodatnią liczbę całkowitą . Jest to długość lewej strony równania — tj. długość słowa utworzonego z cyfr lub i jednoliterowych zmiennych. W następnym wierszu jest zapisana lewa strona równania jako ciąg cyfr lub zmiennych bez odstępów między nimi. Następne dwa wiersze zawierają opis prawej strony równania. Pierwszy z tych wierszy zawiera dodatnią liczbę . Jest to długość prawej strony równania. Drugi z wierszy zawiera prawą stronę równania zapisaną w taki sam sposób jak jego lewa strona. Liczba cyfr plus suma długości wszystkich zmiennych (licząc wszystkie wystąpienia każdej zmiennej) po każdej stronie równania nie przekracza .

Wyjście

Dla każdego , , Twój program powinien zapisać w -tym wierszu standardowego wyjścia liczbę różnych rozwiązań -tego równania.

Przykład

Dla danych wejściowych:

1
5
4 2 4 4 2
5
1bad1
4
acbe

poprawną odpowiedzią jest:

16

Autor zadania: Wojciech Rytter.