欧雷尔斯和右方之火失败了。等到上条当麻赶到时，欧雷尔斯中了妖精化而失去魔神之力，身受重伤，生死不明。右方之火也完全不知所踪。
而被他们打入妖精化的欧提努斯，却从 $50\%$ 可能性的不完美魔神，变成了 $100\%$ 失败的，另一种全盛魔神。
「小场面战斗什么的太麻烦啦。就让我令世界终结吧！」如她所言。紧接着，一切都毁灭了。
当麻醒来时，发现周围一片漆黑，下面是延伸到无穷远，没有起伏的平面。除了自己和欧提努斯之外什么都没有。
「我所破坏的可不止是“地球”这个渺小的行星而已啊」欧提努斯说道。
当麻认定欧提努斯在撒谎，欧提努斯索性让当麻亲自确认。 当麻走在一片黑暗中，不知自己走了多久，直到双腿走到瘫软。只有黑暗和寂静，没有山川河流，没有日月星辰。
欧提努斯深知杀死当麻，幻想杀手还会寄宿在其他人身上。因此只有将当麻的反抗意志抹除，使幻想杀手的力量永远封存在当麻体内，这才是最佳的办法。但欧提努斯是神，没必要为了击溃一个人类的意志亲自动手。就在此时，主神之枪光芒四射，欧提努斯要让当麻亲自领悟到自己先前所做的一切是多么的渺小，世界顿时被光芒笼罩。
当麻在二楼一张床上醒来，这是一个没有天花板的屋子，周围有烧焦的味道，星空如往常一样安宁。屋里的电视机上播放一条新闻：「多国联军发起的剿灭上条当麻的作战正在进行，二十三区七成区域化为废墟，上条当麻生死不明。」
当麻看得一头雾水，这时当麻才注意到城市的大范围停电和四处燃烧着的烈火。电视切换到了美国总统，他声明在确认当麻死亡之前绝不会停止打击。虽然现在无法判断打击上条当麻而牺牲无辜者的行为是否正义，但百年后的人们一定会称赞这种行为。因为如果现在放过上条当麻，百年后将只剩下废墟和残骸。就在当麻猜测这是引诱『格雷姆林』的情报战时，欧提努斯出现在当麻身后，她拿出遥控器切换电视节目。各国首脑都在报道当麻的罪恶以及杀死当麻的决定。
「你对那些人做了什么！」当麻大喊道。欧提努斯称并没有威胁他们，这不是梦境和幻觉，而是欧提努斯创造出来的现实世界，并提醒当麻再不离开这里就会死。此时俩个人提着手电赶来，来调查电视为何开着。他们砸碎了玻璃，当麻找地方藏起来。但万万没想到他们并未进屋，而是往屋内放火。当麻从二楼跳出去，在着陆后，有人朝当麻开枪，当麻注意到那俩人居然是警察。当麻甩开他们后躲在电线杆处休息，欧提努斯站在电线杆顶部庆祝当麻通过了最初试炼，并告诉当麻自己什么都没做，只是将立场改变而已。
欧提努斯的声音响起，「在你用拳头击倒敌人而保护别人时，在你为结束三战立下不可磨灭的功劳时，你被当做英雄，理所当然地受到追捧，正面完全掩盖了负面，这是原来的世界。但如果将立场改变，你对每个反对自己意见的人都会施加拳脚，甚至用拳脚影响整个三战走向，这种行为比那些独裁者有过之而无不及，这就是现在的世界。我并没有给那些人洗脑，而只是将你的负面展现给世人罢了。」
当麻在路上看到很多人因饥饿而死，昔日的城市变成废墟。紧接着，多国联军对所有可能藏匿当麻的地方展开空袭，接纳逃难学生的地方均被轰炸。当麻急于确认父母的安全，突然一把菜刀插进当麻背部，当麻倒地不起，小萌老师拔出菜刀，向上条道歉，但她不能容忍其他同学受罪。远处的电视出现了当麻父母的身影，父母在电视上公开承认当麻是他们的儿子。小萌拿着带血的刀，流着泪再度走向上条。
当麻的父母在电视上请求让他们夫妻俩亲自处决儿子，并请求大家原谅自己生下当麻的罪孽。当小萌再度举刀时，欧提努斯蹲在当麻面前问当麻，「人们都是在看到你的名字，外表和事迹之后，就擅自认定你是什么样的人了。然而只要改变一下立场，就算你做的事情并没有丝毫改变，他们依旧会烧你，追你，打你甚至杀你，如果有人能正确看待你，那至少也会有一个人来救你吧。然而到头来，没有一个人了解真实的你。这样的人，值得救吗？」
当麻依旧回答，「就算这样，也有救他们的价值。」
欧提努斯表示当麻简直无可救药。然后打了个响指，小萌挥下菜刀……
当麻睁开眼睛，发现自己在午休时趴在课桌上睡着了。而自己的身体并没有受伤，原来是个噩梦啊！当麻舒了口气。
接着，当麻发现，一个和当麻的身高，体重，五官，发色完全不同的人，却被众人当成了真正的上条当麻。而上条当麻本人，却独自一人坐在教室的一处不被任何人注意的椅子上……
这便是欧提努斯为了摧毁上条当麻的意志，所创造的『无限地狱』：不断创造新的世界，否定当麻存在的意义，再用不同的方式杀死他，摧毁这个世界。
当麻也曾想过放弃，但最终，他决定遵从自己的意志，向魔神挑战。即便欧提努斯动动手指便可以杀死他，即便已经死了数千亿次。
在其中一个世界，欧提努斯给了当麻 $1\sim n$ 的所有整数。
当麻要将这些数划分成三个集合（可以为空），要求任意两个属于不同集合的元素之和不在剩下的那个集合之内。集合之间是无序的。
如：$\left\{4\right\},\left\{2,6\right\},\left\{1,3,5\right\}$ 是 $n=6$ 时的合法划分方案。而 $\left\{1,2,4\right\},\left\{3,6\right\},\left\{5\right\}$ 却不是，由于 $2+3=5$。
欧提努斯要求当麻计算这样的划分的方案数对 $998244353$ 取模的值，否则就杀死他。
当麻没学过 OI，于是他不会做。但好在，这个世界里还有你的存在，请帮助他求出方案数。
输入格式
一行一个正整数 $n$。
输出格式
输出一行一个整数表示答案对 $998244353$ 取模后的结果。
样例
样例 1 输入
11
样例 1 输出
1092
样例 2 输入
4
样例 2 输出
9
样例 3 输入
514
样例 3 输出
653467211
数据范围与约定
- Subtask 1 (4%): $n \le 10$
- Subtask 2 (13%): $n \le 40$
- Subtask 3 (17%): $n \le 3\,000$
- Subtask 4 (21%): $n \le 10^6$
- Subtask 5 (22%): $n \le 10^9$
- Subtask 6 (23%): $n \le 2 \times 10^{10}$