You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

对于正整数$n$，我们定义 $\text{highbit}(n)$ 为满足 $2^i\leq n$ 的最大的非负整数 $i$。

特殊的， $\text{highbit}(0)=-1$。

小 Y 有一个正整数 $X$ 。

小 Y 称一个正整数可重集 $S$ 是好的，当且仅当：

• $S$ 的所有元素都是 $2$ 的非负次幂。
• $S$ 的元素之和为 $X$ 。
• 不存在一种将 $S$ 分成两个集合 $S_1,S_2$ 的方法，使 $\text{highbit}(Sum_1)=\text{highbit}(Sum_2)$，其中 $Sum_1$ 是 $S_1$ 中元素的和，$Sum_2$ 是 $S_2$ 中元素的和。

现在想知道对于 $X$ ，有多少个好的可重集 $S$。答案对 $998244353$ 取模。

输入格式

从 divide.in 文件读入数据。

一行一个整数 $n$。

输出格式

输出到 divide.out 文件。

输出一行 $n$ 个数，第 $i$ 个数代表 $X=i$ 的答案。

样例 1

10

1 1 2 1 1 3 6 1 1 2 

数据范围

对于每个测试点， 保证 $1\le n\le 10^6$