#P18140. Formal Fring

Formal Fring

Formal Fring

I don't think we're alike at all, Mr. White. You're not a cautious man at all... you have poor judgement. I cannot work with someone with poor judgement.

——Gustavo Fring, Breaking Bad

Gus Fring 是一个非常谨慎的人。他从不和你乱来。当他请人解决一个问题时,他会给出一个完全形式化的题面。今天他找上了你。

对于正整数 nn,定义 highest_bit⁡(n)\operatorname{highest\_bit}(n) 为满足 2i≤n2^i\le n 的最大整数 ii;另外定义 highest_bit⁡(0)=−1\operatorname{highest\_bit}(0)=-1。

给定正整数 XX。求满足以下条件的正整数多重集 SS 的个数:

  • SS 中的每个元素都是 22 的非负整数次幂;
  • SS 中元素之和为 XX;
  • 不存在把 SS 划分成两组的方法,使得两组元素之和 S1,S2S_1,S_2 满足 $\operatorname{highest\_bit}(S_1)=\operatorname{highest\_bit}(S_2)$。

你需要对 X=1,2,…,nX=1,2,\dots,n 分别求出答案。由于答案可能很大,请对 998244353998244353 取模。

输入格式

输入只有一行一个整数 nn(1≤n≤1061\le n\le 10^6)。

输出格式

输出 nn 个整数,依次表示 X=1,2,…,nX=1,2,\dots,n 时的答案(对 998244353998244353 取模)。

样例

输入:

10

输出:

1 1 2 1 1 3 6 1 1 2