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

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.

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.

h2. Restricţii

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

* $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 |

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

|
 
h3. Explicaţie
 
Avem trei lanţuri distincte cu 3 ochiuri din 10 segmente:

|   |

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

5651