Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_15_05 - Gra 2

Staś i Grześ grają w pewną bardzo ambitną grę planszową. Gra polega na tym, że rzucają oni naprzemiennie dwoma standardowymi kostkami do gry (zawierającymi od 1 do 6 oczek na swoich ściankach). Po każdym rzucie dany gracz przesuwa swojego pionka w lewo o taką liczbę oczek jaka wypadła na kostce białej oraz do góry o liczbę oczek jaka została wylosowana na kostce czerwonej. Nasi bohaterowie rozpoczynają grę z pola o współrzędnych 0,0. Grę wygrywa ten z nich, który jako pierwszy dotrze na pole o współrzędnych x,y.

Właśnie Grześ miał ustawić pionka na polu oznaczonym jako meta i świętować zwycięstwo, kiedy Staś krzyknął w jego stronę:
- Oszukujesz! Zapisałem wszystkie wartości jakie wypadały na obydwu kostkach podczas gry i jasno z nich wynika, że Twój pionek nie może znajdować się na polu o współrzędnych x,y!
- Ależ oczywiście, że może - wyniki rzutów na obydwu kostkach jasno wskazują, że mogłem dotrzeć na to pole na dokładnie m sposobów!

Twoim zadaniem jest napisanie programu, który obliczy resztę z dzielenia liczby m przez 1012. Niestety Staś nie zapisał ile razy na poszczególnej kostce wypadła dana liczba w związku z czym należy założyć, że każdy z zapisanych wyników mógł zostać wylosowany nieskończenie wiele razy.

Wejście

W pierwszej linii wejścia znajdują się cztery liczby całkowite h, v, x oraz y (1 ≤ h, v ≤ 6, 1 ≤ x, y ≤ 1000). Liczby h i v opisują odpowiednio ile unikatowych wyników zostało wylosowanych na kostce białej oraz czerwonej. Liczby x,y określają współrzędne pola mety. W drugiej linii wejścia znajduje się h liczb - jest to zbiór wyników na kostce białej. W trzeciej linii wejścia znajduje się v liczb - jest to zbiór wyników na kostce czerwonej.

Wyjście

Na wyjściu należy wypisać liczbę określającą na ile sposobów Grześ mógł dotrzeć na pole mety modulo 1012.

Przykład

Wejście

3 3 3 3
1 2 3
3 2 1

Wyjście

6

Wyjaśnienie do przykładu

Sekwencje rzutów, które umożliwią przejście na pole o współrzędnych 3,3 to:

  • Kostka biała: 1 1 1
    Kostka czerwona: 1 1 1
  • Kostka biała: 1 2
    Kostka czerwona: 1 2
  • Kostka biała: 1 2
    Kostka czerwona: 2 1
  • Kostka biała: 2 1
    Kostka czerwona: 1 2
  • Kostka biała: 2 1
    Kostka czerwona: 2 1
  • Kostka biała: 3
    Kostka czerwona: 3

Dodane przez:Maciej Boniecki
Data dodania:2014-03-29
Limit czasu wykonania programu:0.300s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.