19570번 - 삼각 분할

문제

muse는 정$N$각형 $P_{1}P_{2}\cdots P_{N}$을 가지고 있다. muse는 이 다각형을 삼각 분할하려고 한다. 여기서 삼각 분할이란, 정$N$각형에 대각선을 적절히 그어 삼각형 $N-2$개로 나누는 것을 말한다. 대각선들은 끝점을 제외하고는 서로 교차하지 않는다.

삼각 분할의 가짓수는 매우 많다. muse는 이 삼각 분할의 가짓수를 구하고자 한다.

하지만 여기서 문제가 끝나면 재미없으니, muse는 삼각 분할된 다각형의 각 삼각형에 빨간색 또는 파란색으로 색칠을 하려고 한다. 이때 변으로 맞닿아 있는 인접한 삼각형은 서로 다른 색으로 색칠해야 하고, 정$N$각형의 한 변 $P_{1}P_{2}$가 포함된 삼각형은 빨간색으로 칠해야 한다.

muse는 가능한 모든 삼각 분할 색칠을 그려 놓았다. 이때, 빨간색 영역의 개수는 총 몇 개일까?

입력

$N$이 주어진다. (3ドル \le N \le 10^5$)

출력

삼각 분할 색칠의 가능한 모든 경우에 대해, 빨간색 영역의 개수의 합을 998ドル\ 244\ 353$(소수)로 나눈 나머지를 출력하여라.

제한

힌트