Pascalsches Dreieck

Das Pascalsche Dreieck ist eines der faszinierendsten Konzepte in der Kombinatorik und hat zahlreiche Anwendungsmöglichkeiten. Eine Möglichkeit, es zu nutzen, ist das Bestimmen des Wertes von CnkC_n^k (n über k).

Das Dreieck wird konstruiert, indem man seine zwei Elternelemente addiert. Zum Beispiel wird die 10 in der 6. Zeile durch Addition von 4 und 6 aus der 5. Zeile gebildet.

pascals-triangle-doubles.svg

Bei gegebener Höhe h sollen Sie das Pascalsche Dreieck konstruieren.

Die einzige Zeile der Eingabe enthält die Zahl h.

Die Ausgabe des Programms sollte das Pascalsche Dreieck der Höhe h sein.

Eingabe

Ausgabe

5

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB