Бүхэл $k$$(k>1)$ тооны хувьд $k-bonacci$ гэдэг нь бидний сайн мэдэх Фибоначчи тооны ерөнхий хэлбэр ба дараах чанар бүхий тоог хэлнэ:

• $1≤n
• $F(k,k)=1$
• $n>k$ байх $n$ тооны хувьд $F(k,n)=F(k,n-1)+F(k,n-2)+...+F(k,n-k)$

$k-bonacci$-ийн хувьд зөвхөн $n$, $k$ тоонууд бүхэл үед тодорхойлогдохыг санаарай. Танд $s$ болон $k$ тоонууд өгсөн бол $s$ тоог хэд хэдэн(ядаж хоёр) ялгаатай $k-bonacci$ тоонуудын нийлбэрт тавьна уу.

Оролт

$s$ болон $k$ $(1 ≤ s,k ≤ 10^9;\ k>1)$ тоонууд өгөгдөнө.

Гаралт

Эхний мөрөнд нийлбэрийг элементүүдийн тоо болох $m$ ($m ≥ 2$) тоо байна. Дараагийн мөрөнд нийлбэр нь $s$-тэй тэнцүү байх $m$ ширхэг $k-bonacci$ тоог хэвлэнэ. Оролт бүр боломжит хариутай байх ба хэрэв хэд хэдэн хариу байвал алийг нь ч хэвлэсэн болно.