该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

lyhlyhlyh最近喜欢打一个叫做《dota》的游戏，他据此出了一道题

Description

lyhlyhlyh化身成为一名强大的后期dps英雄，他依靠普通攻击对防御塔造成伤害。
lyhlyhlyh的dota水平极高，并且他还是个码农，因此他能够控制自己每次普通攻击的下手力度并且每次普通攻击对防御塔造成2的某个次幂的伤害。
现在告诉你防御塔的血量n，求lyhlyhlyh有多少种方案拆掉防御塔。
不过lyhlyhlyh并不关心他是以一个怎么样的顺序来拆掉防御塔的，也就是说他只关心他使用不同力度攻击的次数。
比如现在有一个体力值为5的防御塔 lyhlyhlyh有如下4种方案拆掉这座塔。
5*(2^0) 五次伤害为2^0的普通攻击
2*(2^1)+1*(2^0) 两次伤害为2^1的普通攻击和一次伤害为2^0的普通攻击
1*(2^1)+3*(2^0) 一次伤害为2^1的普通攻击和三次伤害为2^0的普通攻击
1*(4^2)+1*(2^0) 两次伤害为2^2的普通攻击和一次伤害为2^0的普通攻击

Format

Input

第一行两个整数n 防御塔的血量

Output

一行一个正整数答案，即题目所求ans
输出答案对998244353取模

Sample 1

Input

5

Output

4

Limitation

1s, 32MB for each test case.

Hint

对于全部测试数据，n<=30000000
本题共有10个测试数据点，每个数据点满足如下特殊限制：
测试点1,2,3：n<=10
测试点4,5,6：n<=1000 并且 n 为2 的某个次幂
测试点7,8：n<=1000000
测试点9,10：n<=30000000

Source

lyhlyhlyh