思路与方法

1. 可行性分析

• 每次操作：选取两个相邻字符，翻转后交换（“00”↔“11”，“01”↔“10”）。
• 注意：操作前后“1 的个数”模 2 不变。
• 因此只有当字符串中 1 的个数 $M$ 为偶数时，才有可能通过若干次操作变为全 0；否则无解，不计入和。

2. 单串最优操作数 $f(s)$

• 若 $s$ 中有偶数个 1，记其位置（从左到右）为 $p_1<p_2<\cdots<p_M$。

题目内容

对于仅由 $0$ 和 $1$ 两种字符组成的字符串 $s$ ,定义一次操作为：

选择两个相邻字符，将它们同时取反（即如果字符原本为 $0$ ，将其变成 $1$ ；如果字符原本为 $1$ ，将其变成 $0$ ）。

记 $f(s)$ 为将 $s$ 变为全 $0$ 所需的最少操作次数。若无法变为全 $0$ ，则该字符串的 $f(s)$ 不计。

现在，给定整数 $n$ ，求所有长度为 $n$ 的合法字符串的 $f(s)$ 之和。由于答案可能很大，请将答案对 $998$ $244$ $533$ 取模后输出。

输入描述

输入一个整数 $n(1≦n≦10^9)$ 代表字符串长度。

输出描述

输出一个整数，代表所有长度为 $n$ 的字符串的 $f(s)$ 之和。由于答案可能很大，请将答案对 $998$ $244$ $533$ 取模后输出。

样例1

输入

2

输出

1

说明

在这个样例中，当 $n =2$ 时，全部的合法字符串有：

• “$00$”，由于不需要任何操作，$f=0$；

• ”$01$“，无法变为全 $0$ ，不计；

• “$10$”，无法变为全 $0$ ，不计；

• “$11$”，操作一次即可，所以 $f=1$ 。

样例2

输入

4

输出

12

样例3

输入

10000

输出

528897405