Albinuţa Zumzi locuieşte într-un stup format din N celule de formă hexagonală. Cele N celule numerotate de la 1 la N sunt dispuse sub formă de spirală ca în figura alăturată.
Adică, celula din centrul stupului este numerotată cu 1. Plecând de la această celulă spre sud şi apoi în spirală, în sensul acelor de ceasornic, sunt numerotate celelalte celule.
Iniţial Zumzi se găseşte în celula din centru (cea numerotată cu 1), şi doreşte să ajungă, trecând din celulă în celulă, la celula cu numărul de ordine X, unde se găseşte prietenul ei. Zumzi se poate deplasa dintr-o celulă în oricare dintre celulele vecine, fără a părăsi însă stupul. Două celule sunt vecine dacă au o latură comună.
Unele celule ale stupului sunt ocupate de alte albine şi de aceea Zumzi nu poate să treacă prin ele.
Cerinţă
Problema vă cere să determinaţi câte variante are Zumzi ca după exact K paşi să ajungă la prietenul ei.
Date de intrare
Fişierul de intrare zumzi.in conţine pe prima sa linie valorile naturale N, M, K, X separate printr-un spaţiu, având următoarea semnificaţie:
- N - numărul total de celule din stup;
- M - numărul de celule din stup ocupate de alte albine
- K - numărul de paşi pe care îi are la dispoziţie Zumzi
- X - numărul de ordine a celulei în care se găseşte prietenul lui Zumzi.
Următoarea linie a fişierului de intrare conţine M numere naturale separate printr-un spaţiu reprezentând numerele de ordine ale celulelor ocupate din stup.
Date de ieşire
Fişierul text zumzi.out va conţine pe prima sa linie un singur număr natural reprezentând numărul de variante pe care le are zumzi la dispoziţie de a ajunge la prietenul ei.
Restricţii
1 <= M < N <= 300
X<>1
K<=100
Zumzi nu are posibilitatea de a părăsi stupul, iar în plus odată ajunsă la prietenul ei nu îl va mai părăsi.
Zumzi nu este o albină foarte inteligentă de aceea ea poate trece de mai multe ori printr-o celulă, cu exceptia celulei finale, in care se afla prietenul ei, celula in care va intra o singura data si nu o mai paraseste.
Exemple
zumzi.in
zumzi.out
Explicaţii
12 4 3 9
11 4 6 8
4
Variantele sunt: 1-2-10-9
1-3-2-9
1-3-10-9
1-7-2-9
12 4 4 2
11 4 6 8
9
Variantele sunt: 1-3-10-9-2
1-7-1-3-2
1-5-1-7-2
etc
