Числа k-боначчи (k целое, k > 1) являются обобщением чисел Фибоначчи и определяются следующим образом:
- F(k, n) = 0, для целых n, 1 ≤ n < k;
- F(k, k) = 1;
- F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k), для целых n, n > k.
Обратите внимание, мы определяем числа k-боначчи, F(k, n), только для целых значений n и k.
Вам задано число s, представьте его в виде суммы нескольких (хотя бы двух) различных чисел k-боначчи.
Выходные данные
В первую строку выведите целое число m (m ≥ 2) — количество чисел в найденном представлении. Во вторую строку выведите m различных целых чисел a1, a2, ..., am. Каждое выведенное число должно быть числом k-боначчи. Сумма выведенных чисел должна быть равна s.
Гарантируется, что ответ существует. Если существует несколько ответов, разрешается вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
|
3
0 2 3
|
|
2
|
21 5
|
3
4 1 16
|