Avem la dispoziţie m segmente, toate de aceeaşi lungime. Din aceste segmente se pot construi poligoane închise de lungime 3, 4, 5, etc… pe care le vom numi ochiuri.
Aceste ochiuri vor fi legate între ele cu ajutorul a 0, 1 sau mai multe segmente. Un astfel de lanţ obţinut întotdeauna începe şi se termină cu un ochi. Exemplele de mai jos reprezintă câte un lanţ format cu 3 ochiuri din 16 segmente.
Două lanţuri se consideră echivalente dacă conţin acelaşi număr m de segmente, acelaşi număr k de ochiuri şi ochiurile corespondente au aceeaşi dimensiune şi sunt legate de acelaşi număr de segmente. Dacă două lanţuri nu sunt echivalente, le vom numi diferite.
Lanţurile din exemplele 1 şi 2 sunt echivalente, iar lanţurile din exemplele 3 şi 4 diferă de celelalte trei lanţuri.
Cerinţă
Să se determine numărul de lanţuri diferite formate din m segmente şi având k ochiuri.
Date de intrare
Fişierul lant1.in conţine pe o singură linie cele două numere naturale m şi k separate printr-un spaţiu.
Date de ieşire
Fişierul lant1.out va conţine un singur număr natural, reprezentând numărul lanţurilor distincte modulo 666013.
Restricţii
• m ≤ 6 00 000
• k ≤ m / 3
Exemple
lant1.in
lant1.out
Explicaţii
10 3
3
Avem trei lanţuri distincte cu 3 ochiuri din 10 segmente:
