题目描述

给定一个正整数 $N \leq 10^9$，请构造一个仅包含 0 和 1 的矩阵 $A = (a_{i,j})_{1 \leq i,j \leq n}$，满足

• $1 \leq n \leq 200$；
• $\det(A) = N$。

保证在问题约束下存在有效的解决方案。

输入格式

输入仅包含一个正整数 $N$ ($1 \leq N \leq 10^9$)。

输出格式

输出应包含第一个正整数 $n$ ($1 \leq n \leq 200$)，表示构造的矩阵的大小。

接下来，输出 $n$ 行，其中第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ ($a_{i,j} \in \{0,1\}$)，表示矩阵第 $i$ 行的元素。如果有多个解决方案，可以输出其中任何一个。

1

1
1

5

7
0 0 0 1 0 0 1
0 0 1 0 0 1 0
0 1 1 0 0 0 1
0 1 0 1 1 0 0
1 1 0 1 1 1 0
1 1 1 1 0 0 0
1 1 1 0 1 0 0