Kolorowanie

Limit pamięci: 32 MB

W pola kratownicy o wymiarach wpisano liczby od do , każdą z nich dokładnie dwukrotnie i tak, aby w każdej kolumnie znalazły się dwie różne liczby. Przykład takiego wypełnienia znajduje się na poniższym rysunku.

Chcielibyśmy teraz pokolorować każde z pól na biało lub szaro tak, żeby pola znajdujące się w tej samej kolumnie uzyskały różne kolory oraz żeby pola zawierające tę samą liczbę uzyskały różne kolory. Przykład takiego pokolorowania kratownicy z poprzedniego rysunku - poniżej.

Na ile różnych sposobów można to wykonać?

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (). Każdy z kolejnych dwóch wierszy zawiera liczb całkowitych z przedziału , pooddzielanych pojedynczymi odstępami. Liczby te reprezentują liczby wypełniające kolejne pola kratownicy.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - liczbę sposobów pokolorowania kratownicy dwoma kolorami w opisany powyżej sposób.

Przykład

Dla danych wejściowych:

5
1 5 3 1 5
4 2 2 4 3

poprawną odpowiedzią jest:

4

Zauważ, że przykład opisuje kratownicę z powyższych rysunków.

Autor zadania: Krzysztof Diks.