걸어서 트리속으로 timer 1s memory 1024MB

시사 교양 프로그램 '걸어서 트리속으로'의 PD인 종경이는 N개의 나라를 한 번씩 촬영하려고 한다. 각 나라의 번호는 1번부터 N번까지이다. 두 나라를 잇는 N-1개의 양방향 직항 항공편이 있으며, 각 나라에서 모든 나라로 비행기를 통해 이동할 수 있다. 한 나라에서 다른 나라로 이동할 때는 비행기만 이용해야 하며, 비행기 탑승 횟수를 최소화하는 방법으로 이동해야 한다.

종경이는 촬영 순서를 잘 정하여 시청률을 높이고자 한다. 이를 위해 N개 나라의 순서 A[0]\rightarrow A[1]\rightarrow \cdots \rightarrow A[N-1]는 다음 조건을 추가로 충족해야 한다.

•  0 \le i < N인 모든 i에 대해, \text{dist} (A[i], A[i+1]) + \text{dist} (A[i+1], A[i+2]) \neq \text{dist} (A[i], A[i+2]) (단, A[N] = A[0], A[N+1] = A[1])

단, \text{dist} (x, y)는 x번 나라에서 y번 나라로 이동할 때, 비행기에 탑승하는 최소 횟수를 나타낸다.

바쁜 종경이를 대신하여, 나라들의 순서를 정하는 방법의 수를 998\,244\,353으로 나눈 나머지를 구해주자.