Misie

Limit pamięci: 32 MB

Bajtocka firma 0101010 produkuje zabawki dla dzieci. 0101010 jest bardzo znaną firmą, a ich zabawki mają opinię bardzo solidnych. Pracownicy firmy z przerażeniem stwierdzili, że ostatnie cztery modele misiów: , , i mają ukrytą wadę: jeśli weźmiemy trzy misie, które wszystkie mają tę samą literę w oznaczeniu modelu, lub wszystkie mają tę samą cyfrę w oznaczeniu modelu i ustawimy je obok siebie w rzędzie, to misie ulegną nieodwracalnemu uszkodzeniu.

Ustawienie misiów w rzędzie nazwiemy bezpiecznym, jeśli w jego wyniku żaden miś nie ulegnie uszkodzeniu, tzn. żadne trzy kolejne misie nie będą wszystkie miały tej samej litery w oznaczeniu modelu, ani tej samej cyfry.

Bajtazar ma kolekcję misiów, w której znajdują się tylko feralne modele. Bajtazar bawi się misiami ustawiając je w rzędzie. Zastanawia się, ile jest możliwych bezpiecznych ustawień misiów. Napisz program, który pomoże mu to ustalić.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę misiów każdego modelu,
• obliczy liczbę bezpiecznych ustawień misiów w rzędzie, modulo ,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym i jedynym wierszu wejścia znajdują się cztery nieujemne liczby całkowite: , , , , oddzielone pojedynczymi odstępami (). Oznaczają one liczbę misiów, odpowiednio modelu , , i . Możesz założyć, że sumaryczna liczba misiów jest dodatnia.

Wyjście

W pierwszym i jedynym wierszu wyjścia Twój program powinien wypisać liczbę dobrych ustawień misiów w rzędzie modulo .

Przykład

Dla danych wejściowych:

0 1 2 1

poprawną odpowiedzią jest:

6

Istnieje 6 poprawnych ustawień misiów: , , , , oraz .

Autor zadania: Maciej Jaśkowski.