Biological Software Utilities

당신은 Biological Software Utilities(BSU)라는 소프트웨어 키트를 개발하고 있다. 이 키트에는 트리 인식을 전문으로 하는 프로그램이 들어 있다. 트리는 사이클이 없는 연결 무향 그래프를 말한다.

자연에서 트리가 자랄 때는 이웃한 두 정점이 동시에 추가된다. 따라서 어떤 트리에서 간선 몇 개를 제거한 결과 그래프가 정점 $2$개짜리 연결 성분만으로 이루어지면 그 트리를 그럴듯하다고 본다. 다시 말해 트리가 그럴듯한 것과 완벽 매칭을 가지는 것은 서로 동치이다.

이제 BSU에 새로운 기능을 구현해, $1$부터 $n$까지 서로 다른 정수로 번호가 붙은 정점 $n$개짜리 그럴듯한 트리의 개수를 구하려 한다. 두 트리는 한쪽에만 있는 간선 $(u, v)$가 존재하면 서로 다른 것으로 본다.

그럴듯한 트리의 개수는 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구한다.

첫째 줄에 트리의 정점 수 $n$이 주어진다 ($1 \le n \le 10^6$).

정점 $n$개짜리 그럴듯한 트리의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.