!problema/urat?x.PNG!

p<>. Pentru orice tip de gard se calculează diferenţele în valoare absolută dintre înălţimile oricăror două scânduri vecine din gard. Suma acestor diferenţe se numeşte _gradul de urâţenie_ al gardului. În exemplul anterior, pentru $n = 3$, se observă că gardurile au în $4$ cazuri gradul de urâţenie egal cu $3$ şi în $2$ cazuri au gradul de urâţenie egal cu 2.

p<>. Pentru orice tip de gard se calculează diferenţele în valoare absolută dintre înălţimile oricăror două scânduri vecine din gard. Suma acestor diferenţe se numeşte _gradul de urâţenie_ al gardului. În exemplul anterior, pentru $n=3$, se observă că gardurile au în $4$ cazuri gradul de urâţenie egal cu $3$ şi în $2$ cazuri au gradul de urâţenie egal cu 2.

h2. Cerinţă

h2. Date de ieşire

Fişierul $urat.out$ va conţine trei linii:
 
* pe prima linie se va scrie un număr natural reprezentând gradul maxim de urâţenie al unui gard format din $n$ scânduri;
* pe a doua linie se va scrie un număr natural reprezentând restul modulo $543217$ al numărului de garduri cu grad maxim de urâţenie care se pot construi folosind cele $n$ scânduri;
* pe a treia linie se vor scrie $n$ numere naturale, oricare două consecutive separate prin câte un spaţiu, reprezentând, în ordine de la stânga spre dreapta, înălţimile scândurilor dintr-un gard cu grad maxim de urâţenie format cu cele $n$ scânduri.

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

h2. Restricţii

* $1 < n &le; 500 000$
* Pentru prima cerinţă se acordă $20%$ din punctaj, pentru a doua $60%$ iar pentru a treia $20%$

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

h2. Exemplu