lant2

Lant2

== include(page="template/taskheader" task_id="lant2") ==

Poveste şi cerinţă...

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.
 
!problema/lant2?poligoane.jpg!
 
Aceste ochiuri vor fi legate între ele cu ajutorul a $0$ 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.
 
!problema/lant2?exemplu1.jpg! !problema/lant2?exemplu2.jpg! !problema/lant2?exemplu3.jpg! !problema/lant2?exemplu4.jpg!
 
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.
 
Să se determine numărul de lanţuri diferite formate din $m$ segmente şi având $k$ ochiuri.

h2. Date de intrare

Fişierul de intrare $lant2.in$ ...

Fişierul $lant2.in$ conţine pe o singură linie cele două numere naturale $m$ şi $k$ separate printr-un spaţiu.

h2. Date de ieşire

În fişierul de ieşire $lant2.out$ ...

Fişierul $lant2.out$ va conţine un singur număr natural, reprezentând numărul lanţurilor distincte modulo $666013$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 ≤ m ≤ 600 000$
* $k ≤ m/3$
* Pentru $30%$ din teste $m ≤ 200$.
* Pentru alte $30%$ din teste $m ≤ 1500$.

h2. Exemplu

table(example). |_. lant2.in |_. lant2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. lant2.in |_. lant2.out |_. Explicatie |
| 10 3
| 3
| Avem trei lanţuri distincte cu 3 ochiuri din 10 segmente:
!problema/lant2?explicatie1.jpg! !problema/lant2?explicatie2.jpg! !problema/lant2?explicatie3.jpg!  |
| 21 4
| 2520
|   |

...

== include(page="template/taskfooter" task_id="lant2") ==

5651