#include <bits/stdc++.h>   using namespace std;   const int mod = 998244353;   const int maxN = 131079;   inline int pls(int x, int y) { return (x + y) % mod; }   inline int mns(int x, int y) { return pls(x, mod - y); }   inline int mul(int x, int y) { return 1LL * x * y % mod; }   inline void Add(int &x, int y) { x = pls(x, y); }   inline void Mul(int &x, int y) { x = mul(x, y); }   inline void Minus(int &x, int y) { x = mns(x, y); }   inline int pwr(int x, int tms) {     int res = 1;     for (; tms > 0; tms >>= 1) {       if (tms & 1) Mul(res, x);       Mul(x, x);     }     return res;   }   inline int inv(int x) { return pwr(x, mod - 2); }   template <class T>   inline T rd() {     bool f = 1;     char c = getchar();     for (; !isdigit(c); c = getchar())       if (c ==  - ) f = 0;     T x = 0;     for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;     return f ? x : -x;   }   int n;   int g[maxN];   int f[2][2][maxN];   int h[2][2][maxN];   namespace poly {   int g[2], pwg[2][maxN];   int L, ivL, rev[maxN];   void init() {     g[1] = inv(g[0] = 3);     for (int i = 2; i < maxN; i <<= 1) {       pwg[0][i] = pwr(g[0], (mod - 1) / i);       pwg[1][i] = pwr(g[1], (mod - 1) / i);     }   }   void getL(int len) {     for (L = 2; L <= len; L <<= 1)       ;     ivL = inv(L);     for (int i = (0), _ = (L); i < _; ++i)       rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (L >> 1) : 0);   }   inline void cpy(int *a, int *b, int len) {     for (int i = (0), _ = (len); i <= _; ++i) a[i] = b[i];   }   inline void clr(int *a, int l, int r) {     for (int i = (l), _ = (r); i <= _; ++i) a[i] = 0;   }   inline void mov(int *a, int *b, int len) {     for (int i = (0), _ = (L); i < _; ++i) a[i] = (i <= len) ? b[i] : 0;   }   void NTT(int *a, int kd) {     int i, j, k, u, v, W, Wn;     for (int i = (0), _ = (L); i < _; ++i)       if (i < rev[i]) swap(a[i], a[rev[i]]);     for (i = 2; i <= L; i <<= 1)       for (Wn = pwg[kd][i], j = 0; j < L; j += i)         for (W = 1, k = j; k < j + i / 2; ++k, Mul(W, Wn))           u = a[k], v = mul(a[k + i / 2], W), a[k] = pls(u, v),           a[k + i / 2] = mns(u, v);     if (kd)       for (int i = (0), _ = (L); i < _; ++i) Mul(a[i], ivL);   }   void conv(int *A, int *B, int *C, int n, int m, int lim) {     static int a[maxN], b[maxN];     getL(n + m);     mov(a, A, n), mov(b, B, m);     NTT(a, 0), NTT(b, 0);     for (int i = (0), _ = (L); i < _; ++i) Mul(a[i], b[i]);     NTT(a, 1);     cpy(C, a, lim);   }   void conv2(int *A, int *C, int n, int lim) {     static int a[maxN];     getL(n + n);     mov(a, A, n);     NTT(a, 0);     for (int i = (0), _ = (L); i < _; ++i) Mul(a[i], a[i]);     NTT(a, 1);     cpy(C, a, lim);   }   void Inv(int *A, int *X, int n) {     static int a[maxN], b[maxN];     if (n == 0) {       X[0] = inv(A[0]);       return;     }     int mid = n >> 1;     Inv(A, a, mid), clr(a, mid + 1, n);     conv2(a, b, mid, n);     conv(b, A, b, n, n, n);     for (int i = (0), _ = (n); i <= _; ++i) X[i] = mns(pls(a[i], a[i]), b[i]);   }   }  // namespace poly   int calc(int a, int b) {     return pls(pls(pls(mul(f[0][0][a], h[0][0][b]), mul(f[0][1][a], h[1][0][b])),                    mul(f[1][0][a], h[0][1][b])),                mul(f[1][1][a], h[1][1][b]));   }   void calc_h(int L, int R) {     static int a[maxN], b[maxN];     if (L == R) {       for (int l = (0), _ = (1); l <= _; ++l)         for (int r = (0), _ = (1); r <= _; ++r) Add(h[l][r][L], f[l][r][L]);       return;     }     int M = (L + R) >> 1;     calc_h(L, M);     for (int l = (0), _ = (1); l <= _; ++l)       for (int m = (0), _ = (1); m <= _; ++m)         for (int r = (0), _ = (1); r <= _; ++r) {           for (int i = (L), _ = (M); i <= _; ++i) a[i - L] = h[l][m][i];           for (int i = (1), _ = (R - L); i <= _; ++i) b[i] = f[m][r][i - 1];           b[0] = 0;           poly::conv(a, b, a, M - L, R - L, R - L);           for (int i = (M + 1), _ = (R); i <= _; ++i) Add(h[l][r][i], a[i - L]);         }     calc_h(M + 1, R);   }   int main() {     poly::init();     n = rd<int>();     g[0] = 1, g[2] = g[4] = mod - 1;     poly::Inv(g, g, n);     for (int i = (0), _ = (n); i <= _; ++i) {       Add(f[0][0][i], g[i]);       Add(f[0][1][i + 1], g[i]);       Add(f[1][0][i + 1], g[i]);       Add(f[1][1][i + 2], g[i]);     }     for (int i = (0), _ = (n); i <= _; ++i)       for (int l = (0), _ = (1); l <= _; ++l)         for (int r = (0), _ = (1); r <= _; ++r) Mul(f[l][r][i], mul(i, i));     calc_h(0, n);     int res = 0;     for (int i = (2), _ = (n); i <= _; ++i)       Add(res, mul(i - 1, calc(i - 2, n - i)));     Add(res, mul(n, pls(f[0][0][n - 1], f[1][1][n - 1])));     printf( %d n , res);     return 0;   }   