题目描述

小华非常喜欢吃布丁。这一天她打算购买原味和抹茶味两种布丁，共n个，之后按照一定顺序将n个布丁全部吃完。

然而如果小华连续吃到三个同口味的布丁，她会感到厌腻而无法继续吃。请你帮助小华规划吃布丁的每一种可行的口味顺序，使她能够全部吃完而不产生厌腻感。

输入格式

输入一个数n，表示布丁的数量。

输出格式

第一行输出一个方案数。

接下来每行输出一个由'0'和'1'组成的字符串，表示一种可行的吃布丁的顺序。其中0表示原味，1表示抹茶味。 请将可行的每种方案按字典序升序输入。

样例数据

input

3

output

6

001

010

011

100

101

110

数据规模与约定

对于100%的数据，1<=n<=20；

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$