Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.
Входные данные
Вводится одно число N (1≤N≤30).
Выходные данные
Выведите N строк треугольника Паскаля.
Примечание
Все числа в треугольнике Паскаля при указанных ограничениях
входят в Longint.
| Пример ввода | Пример вывода |
8 |
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 |