题目描述

科技馆里有一面会“生长”的数字灯墙。第一层只有一个数字 1。从第二层开始，每层最左边和最右边都是 1，中间的每个数字等于它左上方与右上方两个数字之和。

给出层数 $n$，请输出这面灯墙的前 $n$ 层。

输入格式

第一行包含一个正整数 $n$。

输出格式

输出 $n$ 行。第 $i$ 行输出 $i$ 个整数，相邻整数之间用一个空格隔开。

5

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

数据范围与提示

• $1\le n\le 20$