题目描述

你有一个大问题！你可能过于喜欢递推关系了。实际上，你十分喜欢正线性递推关系（positive linear recurrence relations, PLRR），可以按如下方式定义。首先选取关系的阶数 $k$。然后选取系数 $c_1,c_2,\ldots,c_k$ 和序列的前 $k$ 个元素 $a_1,a_2,\ldots,a_k$。如果所有这些数都是正整数，则这个关系被称为「正」的。序列的其余部分可以用如下公式无限生成

$$a_{i+k}=c_1\cdot a_i+c_2\cdot a_{i+1}+\ldots+c_k\cdot a_{i+k-1} \quad \text{for} \quad i\ge 1 $$

Fibonacci 数列是这种形式的最有名的递推数列，但是还有其他很多。

事实上，昨天你数学灵感乍现，在一些卡片上写下了所有可能的正线性递推关系，以及每个关系对应的无穷序列，每张卡片写了一个。（你有很多卡片；成批买的）这一切都有点模糊。但是当你今天醒来的时候，你意识到你没有一个好的方法来对 PLRR 进行排序或计数。你试过按序列的字典序排序，但以 $1$ 开头的序列太多了，你永远也数不清后面的序列。

幸运的是，灵感再次乍现！你们意识到，可以只按序列中生成的部分（即序列中从初始的 $k$ 个值之后开始的部分）的字典序顺序排列 PLRR。并用系数的字典序打破相等局面。例如，$k = 1,c_1 = 2,a_1 = 2$ 在 $k = 2, (c_1, c_2) = (2, 1),(a_1, a_2) = (1, 2)$ 之前，即使两者序列的生成部分相同。这样你就可以从 $1$ 开始，为每张卡片分配一个编号，从而正确地为卡片创建索引了。

给定卡片的索引，请描述写在这张卡片上的序列！

输入格式

输入包含一行一个整数 $n$（$1\le n\le 10^9$），表示要求的 PLRR 的编号。

输出格式

输出四行，表示要求的递推关系。第一行包含它的阶数 $k$。第二行包含 $k$ 个系数 $c_1,\ldots,c_k$。第三行包含 $k$ 个初始值 $a_1,\ldots,a_k$。第四行包含前 $10$ 个生成值。

3

2
1 1
1 1
2 3 5 8 13 21 34 55 89 144

1235

4
1 1 3 1
3 2 1 1
9 15 44 99 255 611 1519 3706 9129 22377