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.|

MWP6_1H - Gra

Stasiowi i Grzesiowi znudziła się już gra w "kamień, papier i nożyce", w związku z czym postanowili zagrać w pewną bardzo ambitną grę planszową. Zasady gry są następujące. Staś i Grześ rzucają naprzemiennie kostką zawierającą 100 ścian ponumerowanych od 1 do 100. Po swoim rzucie każdy z nich przesuwa pionka po planszy o tyle pól do przodu ile wypadło na kostce. Wygrywa ten z nich, który jako pierwszy dotrze do mety znajdującej się na k-tym polu. Chłopcy startują z pola o numerze 0.

Właśnie Grześ miał stanąć 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 kostce przy Twoich rzutach i widać po nich, że Twój pionek nie może znajdować się na k-tym polu!
- Ależ oczywiście, że może. Wyniki moich rzutów jasno wskazują że mogłem dotrzeć na pole o numerze k 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 wypadła na kostce 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ę dwie liczby całkowite w oraz k (1 ≤ w ≤ 100, 1 ≤ k ≤ 1000). Liczba w opisuje ile unikatowych wyników wyrzucił Grześ na kostce w trakcie gry, liczba k natomiast oznacza pole na którym znajduje się jego pionek (możliwość dotarcia do tego pola wzbudza wątpliwości Stasia). W drugiej linii wejścia znajduje się w liczb - jest to zbiór wyników rzutów Grzesia.

Wyjście

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

Przykład

Wejście

4 10
2 3 5 8

Wyjście

16

Wyjaśnienie do przykładu

Sekwencje rzutów, które umożliwią przejście na pole o numerze 10 to:

  • 2 2 2 2 2
  • 2 2 3 3
  • 2 3 2 3
  • 2 3 3 2
  • 3 2 2 3
  • 3 2 3 2
  • 3 3 2 2
  • 2 3 5
  • 2 5 3
  • 3 2 5
  • 3 5 2
  • 5 2 3
  • 5 3 2
  • 5 5
  • 2 8
  • 8 2

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

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