urat

Avem la dispoziţie $n$ scânduri de înălţimi $1$, $2$, $3$, ..., $n$. Vrem să construim un gard aşezând scândurile una lângă alta într-o ordine întâmplătoare. De exemplu, dacă $n=3$, putem să construim gardul în $6$ moduri:

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

Cerință

Cunoscând numărul $n$ de scânduri, realizaţi un program care:

• calculează gradul maxim de urâţenie pe care îl poate avea un gard de $n$ scânduri;
• calculează restul modulo $543\ 217$ al numărului de garduri cu grad maxim de urâţenie care se pot construi cu cele $n$ scânduri;
• determină un gard cu grad maxim de urâţenie format din $n$ scânduri, sub forma unei permutări de ordin $n$.

Date de intrare

Fişierul urat.in conţine pe prima linie numărul natural $n$ reprezentând numărul de scânduri.

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 $543\ 217$ 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.

Restricții și precizări

• $1 \lt n \le 500\ 000$
• Pentru prima cerinţă se acordă $20\%$ din punctaj, pentru a doua $60\%$ iar pentru a treia $20\%$.

Exemplu

urat.in

3

urat.out

3
4
1 3 2

Explicație

Gradul maxim de urâţenie este $3$.
Există $4$ tipuri de garduri cu grad maxim de urâţenie dintre cele $6$ cazuri posibile — vezi figura de mai sus.
Unul dintre gardurile de urâţenie maximă foloseşte, de la stânga la dreapta, scândurile de înălțimi $1$, $3$, $2$ — vezi al doilea gard din figură.