题目描述

有一个奇幻的矩阵，在不停的变幻，其变幻的方式为: 数字 0 变成矩阵 $\begin {bmatrix} 0&0\\0&1\\ \end{bmatrix}$，数字 1 变成矩阵 $\begin {bmatrix} 1&1\\1&0\\ \end{bmatrix}$ 。最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样?

例如，矩阵最初为: $\begin {bmatrix} 0\\ \end{bmatrix}$，矩阵变幻 1 次之后成为：$\begin {bmatrix} 0&0\\0&1\\ \end{bmatrix}$，变幻 2 次之后成为：$\begin {bmatrix} 0&0&0&0\\0&1&0&1\\0&0&1&1\\0&1&1&0\\ \end{bmatrix}$。

输入格式

一行一个整数 n ( n <= 10 )

输出格式

一个经过 n 次变幻后的矩阵

样例

2

0 0 0 0
0 1 0 1
0 0 1 1
0 1 1 0