Minimala Fibonaccisummor

Alla positiva heltal kan skrivas som en summa av fibonaccital (t.ex. den triviala lösningen 1+1+1+...+1). Ett svårare problem är att skriva heltalet med så få fibonaccital som möjligt. T.ex. skrivs talet 7 med minsta antal fibonaccital som 2+5, medan 12 skrivs som 8+3+1. Din uppgift är att skriva ett program som gör precis detta!

Input

Den första raden består av ett heltal $1 \le n \le 10^{9}$.

Output

På den första raden ska du skriva ut ett heltal $k$; det minsta antalet fibonaccital du behöver. Sedan ska du skriva ut en sekvens av $k$ stycken fibonaccital vars summa blir $n$. Ditt program ska skriva ut en så kort sekvens fibonaccital som möjligt, sådan att deras summa är lika med $n$.

7

2
5
2

12

3
8
3
1

3

1
3