AlgoLiga 2018

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 10¹². 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 10¹².

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