#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 是一个非常谨慎的人。他从不和你乱来。当他请人解决一个问题时,他会给出一个完全形式化的题面。今天他找上了你。
对于正整数 ,定义 为满足 的最大整数 ;另外定义 。
给定正整数 。求满足以下条件的正整数多重集 的个数:
- 中的每个元素都是 的非负整数次幂;
- 中元素之和为 ;
- 不存在把 划分成两组的方法,使得两组元素之和 满足 $\operatorname{highest\_bit}(S_1)=\operatorname{highest\_bit}(S_2)$。
你需要对 分别求出答案。由于答案可能很大,请对 取模。
输入格式
输入只有一行一个整数 ()。
输出格式
输出 个整数,依次表示 时的答案(对 取模)。
样例
输入:
10
输出:
1 1 2 1 1 3 6 1 1 2