#include #include using namespace std; using mint = atcoder::modint998244353; int main(){ int n; cin >> n; vector> dir = {{1, 1}, {0, 1}, {-1, 1}, {1, 0}, {-1, 0}}; auto check = [&](int i, int j){ auto [dx1, dy1] = dir[i]; auto [dx2, dy2] = dir[j]; dx1 *= -1, dy1 *= -1; return dx1 * dx2 + dy1 * dy2 < 0; }; array A{}; array B; for(int i = 0; i < 5; i++){ for(int j = 0; j < 5; j++){ A[i] |= check(i, j) << j; } B[i] = mint(1) / __builtin_popcount(A[i]); } mint ans; array dp, ndp; dp.fill(mint(1) / 5); ans += 3 * dp[0]; for(int i = 1; i < n; i++){ ndp.fill(0); for(int j = 0; j < 5; j++){ for(int k = 0; k < 5; k++){ if(A[j] >> k & 1) ndp[k] += B[j] * dp[j]; } } swap(dp, ndp); ans += dp[0] + dp[1] + dp[2]; } cout << ans.val() << '\n'; }