#P18147. Huge Segment Tree

Huge Segment Tree

Huge Segment Tree

给定整数K。在整数轴上,称形如

$$[2^i j,\;2^i(j+1))\qquad (0\le i\le K,\ 0\le j<2^{K-i})$$

的半开区间为线段树区间。

对任意整数0≤l<r≤2^K,定义f(l,r)为:用若干线段树区间的并恰好表示[l,r)时,所需区间数量的最小值。

请依次求出,对于k=1,2,…,2K−2,有多少对整数(l,r)满足0≤l<r≤2^K且f(l,r)=k。每个答案对998244353取模。

输入格式

一行一个整数K,2≤K≤500000。

输出格式

按k从1到2K−2的顺序,输出对应的2K−2个答案,以空格分隔。

样例1

输入:

3

输出:

15 14 6 1

只有(l,r)=(1,7)需要4个线段树区间。

样例2

输入:

5

输出:

63 110 132 114 70 30 8 1

样例3

输入:

10

输出:

2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1