爆搜可得答案序列：

$$1,3,5,11,21,43,85,171,341,683,\ldots$$

瞪眼可得公式：

$$A_n=\begin{cases}1,&n=1\\2A_{n-1}-1,&n=2k+1\\2A_{n-1}+1,&n=2k\end{cases}(k \in \mathbb{Z}) $$

化简可得：

$$A_n=\begin{cases}\dfrac{4^{k+1}-1}{3},&n=2k+1\\\\\dfrac{4^{k+1}+2}{6},&n=2k\end{cases}(k \in \mathbb{Z}) $$

实际上这就是 OEIS A001045：

$$A_n=\begin{cases}2n-1,&n\le 2\\A_{n-1}+2A_{n-2},&n\ge 3\end{cases} $$

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
int divs(int a, int b, int p)
{
	if (b % a == 0) return b / a;
	int x = divs(p % a, a - b % a, a);
	return (1ll * x * p + b) / a;
}
int power(int b, int k, int p)
{
	if (k == 0) return 1;
	if (k == 1) return b;
	long long s = power(b, k >> 1, p);
	s = s * s % p;
	if (k & 1) s *= b;
	return s % p;
}
int read()
{
	char c = getchar();
	long long x = 0;
	while (c >= '0')
	{
		x = (x * 10 + c - '0') % (2 * P - 2);
		c = getchar();
	}
	return x;
}
int main()
{
    int n = read();
    int k = n / 2 + 1;
    if (n & 1) cout << 1ll * divs(3, 1, P) * (power(4, k, P) - 1) % P << endl;
    else cout << 1ll * divs(6, 1, P) * (power(4, k, P) + 2) % P << endl;
    return 0;
}