B - Practical Computing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

以下のような N 個の整数列 A_0,\ldots,A_{N-1} を求めてください。

  • 各 i (0\leq i \leq N-1) について、A_i の長さは i+1 である。

  • 各 i,j (0\leq i \leq N-1, 0 \leq j \leq i) について、A_i の j+1 番目の値 a_{i,j} は次のように定められる。

    • j=0 または j=i の時、a_{i,j}=1
    • それ以外の時、a_{i,j} = a_{i-1,j-1} + a_{i-1,j}

制約

  • 1 \leq N \leq 30
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

N 行出力せよ。 i 行目には A_{i-1} の値を順に空白区切りで出力せよ。

入力例 1

3

出力例 1

1
1 1
1 2 1

入力例 2

10

出力例 2

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
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Score : 200 points

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

  • For each i (0\leq i \leq N-1), the length of A_i is i+1.
  • For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
    • a_{i,j}=1, if j=0 or j=i.
    • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

  • 1 \leq N \leq 30
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain the terms of A_{i-1} separated by spaces.

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

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
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1