Days of Floral Colours

The Floral Clock는 오랫동안 Mirror Lake 곁에 서 있었다. 시간을 잴 수는 없지만, 사람들에게 시간의 흐름과 좋았던 옛 시절을 떠올리게 한다.

Floral Clock의 테두리에는 시계 방향으로 1부터 2n까지 번호가 매겨진 2n송이의 꽃이 있으며, 각 꽃은 가능한 n가지 색 중 하나를 가진다. 각 색마다 정확히 두 송이의 꽃이 있으며, 두 꽃 사이의 거리는 2 이하이거나 n이다. 또한 꽃 u와 v가 같은 색이라면, u의 맞은편에 있는 꽃과 v의 맞은편에 있는 꽃도 같은 색이어야 한다. 대칭은 아름답기 때문이다!

형식적으로, 두 꽃 사이의 거리는 두 꽃 사이의 짧은 쪽 호(또는 반원) 위에 있는 꽃의 수에 1을 더한 값이다. 아래에는 n = 6일 때 모든 가능성을 포괄하는 배치가 나와 있다.

배치의 아름다움은 자신과 같은 색인 맞은편 꽃들 모두에 의해 분리되는 꽃 구간들의 길이를 곱한 값으로 정의한다. 다시 말해 아름다움을 계산하기 위해, 원에서 자신의 맞은편 꽃과 같은 색인 모든 꽃을 제거한다. 그러면 아름다움은 남은 모든 구간의 길이를 곱한 값이다. 길이가 0인 구간도 이 곱에 포함한다는 점에 유의하라. 자신의 맞은편 꽃과 같은 색인 꽃이 하나도 없다면 아름다움은 0이다. 예를 들어 위 배치의 아름다움은 1 × 3 × 1 × 3 = 9이다. 구간은 {2}, {4, 5, 6}, {8}, {10, 11, 12}이다.

제약 조건을 만족하면서도 서로 다른 배치가 매우 많이 존재할 수 있다. 가능한 모든 배치에 대한 아름다움의 합을 998 244 353으로 나눈 나머지를 구한다. 두 배치는, 한 배치에서는 꽃 u와 v가 같은 색이지만 다른 배치에서는 같은 색이 아니게 하는 쌍 (u, v) (1 ≤ u, v ≤ 2n)가 존재하면 서로 다른 것으로 간주한다.

입력의 첫 번째이자 유일한 줄에는 외로운 양의 정수 n (3 ≤ n ≤ 50 000)가 주어진다. 이는 Floral Clock에 존재하는 색의 수이다.

가능한 모든 꽃 배치에 대한 아름다움의 합을 998 244 353으로 나눈 나머지인 정수 하나를 출력한다.

n = 3일 때, 다음 여섯 배치는 각각 2 × 2 = 4의 아름다움을 가진다.

한편 아래 그림의 왼쪽 배치와 같은 다른 많은 배치는 아름다움이 0이다. 오른쪽 배치는 비대칭이므로 유효하지 않다.