给定一个整数 $n$。请找出一个最大的由长度为 $n$ 的不同二进制字符串组成的集合，使得集合中任意两个字符串在恰好一个位置上的字符不同。

例如，对于 $n = 5$，字符串 $10001$ 和 $11001$ 不能同时存在于集合中，因为它们仅在第二个位置上不同。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 15$)，表示集合中二进制字符串的长度。

输出格式

输出的第一行应包含一个整数 $k$ ($0 \le k \le 2^n$)，表示你所选集合中字符串的数量。

接下来的 $k$ 行，每行应包含一个长度为 $n$ 的二进制字符串，表示你集合中的一个字符串。

集合中任意两个字符串不能相等，也不能在恰好一个位置上不同。

如果存在多种解，你可以输出其中任意一种。

样例

样例输入 1

1

样例输出 1

1
0

样例输入 2

2

样例输出 2

2
00
11

说明

在第一个样例中，我们选择了集合 $\{0\}$；在第二个样例中，我们选择了集合 $\{00, 11\}$。这两个集合中都不包含在恰好一个位置上不同的两个字符串，并且可以证明它们对于给定的 $n$ 都是最大规模的。