Triang

O triangulație a unui poligon convex este o mulțime formată din diagonale ale poligonului care nu se intersectează în interiorul poligonului ci numai în vârfuri și care împart toată suprafața poligonului în triunghiuri.

Cerință

Fiind dat un poligon cu $n$ vârfuri notate $1, 2, ..., n$ să se genereze toate triangulațiile distincte ale poligonului. Două triangulații sunt distincte dacă diferă prin cel puțin o diagonală.

Date de intrare

În fișierul text triang.in se află pe prima linie un singur număr natural reprezentând valoarea lui $n$.

Date de ieșire

În fișierul text triang.out se vor scrie:

• pe prima linie, numărul de triangulații distincte;
• pe fiecare din următoarele linii codul unei triangulații, în orice ordine. Codul este format cu ajutorul diagonalelor ce compun triangulația. O diagonală va fi precizată prin două numere reprezentând cele două vârfuri care o definesc.
  $\text{cod = } \prod {( \min(d_1,d_2)\cdot 137+\max(d_1,d_2) )} \text{ mod } (10^9+7)$, unde $d_1$ și $d_2$ sunt vârfurile unei diagonale din descompunere, produsul făcându-se peste toate diagonalele din descompunere (se consideră $1$ pentru mulțimea vidă).

Restricții și precizări

• $1 \leq n \leq 16$
• Se acordă $20\%$ din punctaj doar pentru numărul de triangulații distincte
• Enunțul si restricțiile au fost modificate

Exemplu

triang.in

5

triang.out

5
19740
77562
116064
58240
39198

Explicații

Descompunerile sunt:
$(1,3), (1,4)$
$(2,4), (2,5)$
$(5,2), (5,3)$
$(3,5), (3,1)$
$(4,2), (1,4)$

$(137 \cdot 1+3) \cdot (137 \cdot 1 + 4)\text{ modulo }10^9+7=19740$