1356: 渔夫的快乐Terraria之旅
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：131
Solved：16
Description
Terraria中，为了快速获得天顶剑，通常需要对木门进行四次猫猫雕像操作，而渔夫是一个极度懒惰而且健忘的人，他每一天都会等可能的进行一次猫猫雕像操作或者什么都不做，如果存在连续四天，渔夫都对木门进行了猫猫雕像操作，那么渔夫将会获得天顶剑。
为了找到合适的时机使用臭虫剑奇袭渔夫，玩家需要计算到第 $N$ 天，渔夫已经获得天顶剑的概率，对于没有新手教程的Terraria玩家来说，计算概率还是太难了，所以玩家决定计算到第 $N$ 天，渔夫已经获得天顶剑的情况数，但他已经被小怪猪龙鱼公爵撞晕了，你能帮他计算出来吗。
答案可能会很大，所以答案请对 $998244353$ 取模
Input
只有一个正整数 $N$ ，表示到了第 $N$ 天， $(1\le N\le 10^6)$
Output
只有一个非负整数，表示到第 $N$ 天，有多少种情况是渔夫已经获得天顶剑。
Sample Input Copy
5Sample Output Copy
3HINT
如果用 $1$ 表示进行了操作， $0$ 表示没有操作，长为 $N$ 的 $01$ 串表示渔夫的操作情况
样例中， $N=5$
只有 $11110,01111,11111$ 三种情况，所以输出为 $3$
如果你能帮助到玩家，那么他会十分感激你，并把天顶剑 $99\%$ 的力量来源————“短铜剑”交给你