FS의 크리티컬 콘서트

루마니아 땅에서 FS가 전설적인 콘서트를 준비하고 있었다. 그의 대표곡 "Sfântul Trapez"가 무대를 뒤흔들 예정이었고, 모든 팬이 공연을 손꼽아 기다렸다. 그런데 FS는 이번 무대에 특별한 장치를 준비했다. 관객을 즐겁게 할 독특한 게임이었다.

이 음악 게임에서 FS는 콘서트를 나타내는 거대하고 신비로운 그래프를 떠올렸다. 정점은 공연자이고, 간선은 공연자들 사이의 연결이다. 피날레를 위해 FS는 이 연결들의 비밀을 파헤치기로 했다. 그는 그래프에 "critical edge"가 몇 개 있는지 알고 싶었다. 간선을 제거했을 때 연결 요소의 개수가 증가하면, 그리고 그럴 때에만 그 간선을 critical edge라고 그는 정의했다. 즉, 간선을 제거하면 연결 요소의 개수가 늘어난다.

FS는 공연자들로 만들 수 있는 모든 그래프를 떠올리고, 각 그래프에서 critical edge의 개수를 세는 과제를 냈다. 그다음 이 개수들을 모두 더해 총합을 구하려 했다.

FS의 힘찬 목소리와 드라마틱한 연출 속에서, 그의 비트와 그래프 게임의 복잡함이 잊지 못할 음악과 수학의 무대로 어우러졌다.

그래서 과제는 분명하다. 정점이 $n$개인 번호 붙은 모든 그래프에 대해 critical edge 개수의 총합을 구하라. 콘서트의 열기로 수학을 빛내라! 답은 $998\,244\,353$으로 나눈 나머지로 구한다.

첫 줄에 정수 $n$이 주어진다 ($1 \leq n \leq 5 \cdot 10^5$).

정수 하나를 출력한다. 구한 총합을 $998\,244\,353$으로 나눈 나머지이다.