# A plus B to the Nth Power
###### tags: `Easy`
> [name=出題者 : 曾致銘]

## Problem
輸入一個正整數 n, 輸出由 $(a+b)^n$ 組成的多項式的各係數。從 $a^n$, $a^{n-1}b^1$, ..., $a^1b^{n-1}$, $b^n$ 排序。

### Input
正整數 n

### Output
數字陣列滿足 $(a+b)^n$ 的各項係數

### Examples

Input  : 5
Output : 1 5 10 10 5 1

Input  : 10
Output : 1 10 45 120 210 252 210 120 45 10 1

### Hints
#### 帕斯卡三角形

如上圖，每一個數字皆為其上排相鄰兩數之和，且 $(a+b)^n$ 的各項係數即為帕斯卡三角形的第 n + 1 排數字
### Constraints
$0 < n < 32$

## Solution
:::spoiler C++

#include <iostream>
using namespace std;

int main() {
  int n;
  cin >> n;
  int values[n + 1][n + 1];

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < 2; j++) {
      values[i][j * i] = 1;
    }
  }

  for (int i = 2; i <= n; i++) {
    if (i == n) {
      cout << values[i][0] << " ";
    }
    
    for (int j = 1; j < i; j++) {
      values[i][j] = values[i - 1][j - 1] + values[i - 1][j];
      if (i == n) {
        cout << values[i][j] << " ";
      }
    }

    if (i == n) {
      cout << values[i][i] << endl;
    }
  }
}

:::

## Reference
https://en.wikipedia.org/wiki/Pascal%27s_triangle