World Finals | ICPC 2023 Luxor
      47th Annual                                                                                      hosted by
       ICPC World
     Championship                                                                                      AASTMT

                                              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 c1 , c2 , . . . , ck , and the first k elements of
a sequence a1 , a2 , . . . , ak . 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 · ai + c2 · ai+1 + · · · + ck · ai+k−1        for i ≥ 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, (c1 , c2 ) = (2, 1), (a1 , a2 ) = (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 ≤ n ≤ 109 ), 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 c1 , . . . , ck . The third line contains the k starting values a1 , . . . , ak . The
fourth line contains the first 10 of the generated values.

 Sample Input 1                                             Sample Output 1
 3                                                          2
                                                            1 1
                                                            1 1
                                                            2 3 5 8 13 21 34 55 89 144

47th ICPC World Championship Problem E: A Recurring Problem © ICPC Foundation                                       9

                                 World Finals | ICPC 2023 Luxor
   47th Annual                                                                  hosted by
    ICPC World
  Championship                                                                  AASTMT

Sample Input 2                       Sample Output 2
1235                                 4
                                     1 1 3 1
                                     3 2 1 1
                                     9 15 44 99 255 611 1519 3706 9129 22377

47th ICPC World Championship Problem E: A Recurring Problem © ICPC Foundation               10