Fişierul intrare/ieşire:	margele.in, margele.out	Sursă	Algoritmiada 2012, Runda 4
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.2 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Margele

Speriata de evenimentele recente petrecute la salonul unde obisnuia sa mearga, Miruna s-a gandit ca ar fi cazul sa se protejeze impotriva ghinioanelor. Cautand prin pod a gasit cateva carti vechi de vrajitorii care au apartinut candva Boonikutzei. La pagina 666 a celei de a 13-a carti pe care a deschis-o Miruna a gasit vraja cautata:

Pentru a evita descarcarile accidentale de arma se recomanda purtarea unui colier din N margele vopsite in rosu si albastru, astfel incat pentru orice subsecventa de K perle exista cel putin A si cel mult B perle rosii.

Complet intamplator, Miruna a primit mostenire din partea Boonikutzei un colier cu N margele, iar acum se intreaba in cate moduri poate sa il vopseasca astfel incat sa fie protejata.

Date de intrare

Fişierul de intrare margele.in contine pe prima linie 4 numere intregi N, K, A si B avand semnificatia din enunt.

Date de ieşire

În fişierul de ieşire margele.out veti afisa un singur numar intreg, reprezentand numarul total de posibilati de vopsire a margelelor modulo 666013.

Restricţii

• 1 ≤ N ≤ 50
• 1 ≤ K ≤ min(10, N)
• 0 ≤ A ≤ B ≤ K

Exemplu

Explicaţie

Pentru primul exemplu toate cele 2⁵ colorari sunt valide, cu exceptia celor 2 in care folosim o singura culoare.

Cum se trimit solutii?