![](/static/branding/mistrzostwa/map_logo.jpg)
![](/static/branding/mistrzostwa/nask_logo.png)
![](/static/branding/mistrzostwa/cp_logo.png)
![](/static/branding/mistrzostwa/uwr_logo.png)
![](/static/branding/mistrzostwa/fri_logo.png)
![](/static/branding/mistrzostwa/insert_logo.png)
Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2023
Problem description
Na eksperymentalnym poligonie armia US i A skonstruowała ogromne pole minowe złożone z N pól ułożonych jedno za drugim, ponumerowanych kolejnymi liczbami naturalnymi od 1 do N. W każdym z N pól znajdują się groźne miny, których nadepnięcie może mieć fatalne skutki. W trakcie kręcenia sceny filmowej, po niektórych polach przebiegł Chuck Norris i miny tam umieszczone wybuchły. Jednym z pól, na których nie ma już miny (bo wybuchła) jest pole numer 1.
Na polu numer 1 stoi Lao, chiński
tyczkarz. Lao ma trzy tyczki, w tym jedną chińską. Każda z nich pozwala
mu przeskakiwać o określoną liczbę pól do przodu. Przy czym chińskiej
tyczki z uwagi, iż znajduje się na niej napis made in china
można użyć tylko raz.
Twoim zadaniem będzie podanie maksymalnego numeru pola do jakiego może przeskoczyć Lao oraz liczby sposobów, na jakie Lao może doskoczyć na to pole.
Wejście
W pierwszym wierszu wejścia znajdują się cztery liczby naturalne N, A, B i C pooddzielane pojedynczymi odstępami i oznaczające odpowiednio rozmiar pola minowego, długości porządnych tyczek i długość chińskiej tyczki. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych, oddzielonych pojedynczymi odstępami, z których i-ta jest równa 0 lub 1 w zależności od tego czy na polu o numerze i znajduje się mina.
Wyjście
W pierwszym wierszu wyjścia należy wypisać dwie liczby naturalne – maksymalny numer pola, do którego może doskoczyć Lao i reszta z dzielenia liczby sposobów doskoczenia na to pole przez 109 + 7.
Ograniczenia
1 ≤ N ≤ 1 000 000, 1 ≤ A, B, C ≤ N.
Przykład
Input | Output | Explanation |
|
|
Wszystkie możliwe sposoby to: 1 → 2 → 3 → 5 → 7, 1 → 3 → 5 → 7, $1 \stackrel{C}{\to} 5 \to 7$, $1 \to 2 \to 3 \stackrel{C}{\to} 7$, $1 \to 3 \stackrel{C}{\to} 7$. |