ICPC 2023 · Problem E · A Recurring Problem

Time limit: 20 seconds

You have a very big problem! You love recurrence relations, perhaps a bit too much. In particular, you are a fan of positive linear recurrence relations (PLRR), which can be defined as follows. First, you choose the order $k$ of the relation. Then you choose coefficients $c_{1}, c_{2}, . . . , c_{k}$, and the first $k$ elements of a sequence $a_{1}, a_{2}, . . . , a_{k}$. The relation is called “positive” if all of these numbers are positive integers. The rest of the sequence can then be generated indefinitely using the formula

$ai+k =c1\cdot ai+c2\cdot ai+1+\cdot \cdot \cdot +ck\cdot ai+k- 1$ for $i\ge 1.$

The Fibonacci sequence is the most famous recurrence of this form, but there are many others.

In fact, yesterday, in a fit of mad mathematical inspiration, you wrote down all possible ways of choosing a positive linear recurrence relation, and each associated infinite sequence, on some index cards, one per card. (You have a lot of index cards; you buy in bulk.) It has all been a bit of a blur. But when you woke up today, you realized that you do not have a good way to order or count the PLRRs. You tried just sorting the sequences lexicographically, but there are too many that start with “$1$” – you will never make it to the later ones.

Fortunately, inspiration struck again! You realized that you can instead order the PLRRs lexicographi- cally by the generated part of the sequence only (that is, the part of the sequence starting after the initial $k$ values). Ties are broken by lexicographic order of the coefficients. For example $k = 1$, $c1 = 2$, $a1 = 2$ comes before $k = 2$, $(c_{1}, c_{2}) = (2,1)$, $(a_{1}, a_{2}) = (1,2)$, even though the continuation of the sequence is the same for both. This allows you to properly index your cards, starting from $1$, with every card being assigned a number.

Given the number on a card, describe the sequence on it!

Input

The input consists of a single line with an integer $n$ ($1\le n\le 10^{9}$), the index of the desired PLRR.

Output

Output four lines detailing the desired recurrence relation. The first line contains its order $k$. The second line contains the $k$ coefficients $c_{1}, . . . , c_{k}$. The third line contains the $k$ starting values $a_{1}, . . . , a_{k}$. The fourth line contains the first $10$ of the generated values.

Sample Input 1

3

Sample Output 1

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

Sample Input 2

1235

Sample Output 2

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