Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнееиз этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.
Входные данные
Вводится одно число N (0<=N<=30).
Выходные данные
Вывести N строк треугольника Паскаля (числа выводятся через пробел).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
|
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
|