Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Misie (mis)

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.