## Description

$n$ balls stand a row. You can select exactly $m$ groups of them, each consisting either a single ball or two neighbouring balls. Each ball can only be in one group.

for all $m$ in $[1,k]$ you need to output the number of such divisions.

## Tutorial

let $f(n,m)$ to be the answer of selecting $m$ groups in $n$ balls.

let

Because

We have

It can be proved that there exist a $Z$ that for all $n$

Then we have

Therefore

As is obviously that

So we can solve $C_1, C_2$

Then $F_n$ shoud be

Obviously

So there is no need to calculate $Z_2$

And this can be solved in $O(k \log k)$

## Code:

int main() {
using namespace Polys;
int _n = sc.n();
int _k = sc.n();
int k = std::max(3, _k+1);
Poly Delta(k);
Delta = 1;
Delta = 6;
Delta = 1;
Delta = Delta.sqrt();
Poly Z = Delta;
Z += Int(1);
Z += Int(1);
Z *= Int(1) / Int(2);
int n = (_n+1) % MOD;
Z = Z.pow(n,n);
Z *= Delta.inv();
for (int i = 1; i <= _k; ++ i) {
printf("%u ", i <= _n ? static_cast<unsigned>(Z[i]) : 0);
}
return 0;
}