无和集问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


对任意给定的n,计算F(n)的值。

Input

输入数据只有一行,给出1 个正整数n(n≤10)。

Output

将计算出的F(n)的值以及{1,2,,F(n)}的一个n 划分输出。第一行是F(n)的值。接下来的n行,每行是一个无和子集 Si

Sample Input

2

Sample Output

8
1 2 4 8
3 5 6 7

Hint

 

Source