Numbers *k*-bonacci (*k* is integer, *k* &gt; 1) are a generalization of Fibonacci numbers and are determined as follows:
 -  *F*(*k*, *n*) = 0, for integer *n*, 1 ≤ *n* &lt; *k*; -  *F*(*k*, *k*) = 1; -  *F*(*k*, *n*) = *F*(*k*, *n* - 1) + *F*(*k*, *n* - 2) + ... + *F*(*k*, *n* - *k*), for integer *n*, *n* &gt; *k*. 
Note that we determine the *k*-bonacci numbers, *F*(*k*, *n*), only for integer values of *n* and *k*.

You've got a number *s*, represent it as a sum of several (at least two) distinct *k*-bonacci numbers.
The first line contains two integers *s* and *k* (1 ≤ *s*, *k* ≤ 10<sup class="upper-index">9</sup>; *k* &gt; 1).
import sys,io,os
from os import path
from collections import Counter,defaultdict
if(path.exists('input.txt')):
     sys.stdin = open('input.txt','r')
     sys.stdout = open('output.txt','w')
else:
     input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def nexti(fibo,n,k):
     sumi=0
     for i in range(n-k-1,n-1):
        #  print(i)
          sumi+=fibo[i]
     return sumi

def howSum(targetSum,arr,memo):
     if targetSum in memo:
          return memo[targetSum]
     if targetSum==0:
          return []
     if targetSum<0:
          return []
     if len(arr)==0:
          return []
     memo[targetSum]=howSum(targetSum-arr[0],arr[1:],memo)+howSum(targetSum,arr[1:],memo)
     return memo[targetSum]
def main():
     s,k=list(map(int,input().split()))
     fibo=[]
     for i in range(k-1):
          fibo.append(0)
     fibo.append(1)
     for i in range(k+1,52):
          samu=nexti(fibo,i,k)
          fibo.append(samu)
      #    print(samu)
          if samu>1000000009:
               break
     fibo=list(set(fibo))
     fibo.sort()
     memo=defaultdict(list)
     for i in range(len(fibo)):
          memo[fibo[i]]=[fibo[i]]
     for i in range(7):
          se=list(set(howSum(s,fibo,memo)))
          memo=defaultdict(list)
          for i in range(len(se)):
               memo[se[i]]=[se[i]]
          se=howSum(s,se,memo)
     print(len(se))
     print(*list(howSum(s,se,memo)))
  #   print(fibo)





for _ in range(1):
    main()
