Counting Cycles in a Nearly Complete Graph

You are given an undirected complete graph with n vertices. One edge of the graph is removed. Your task is to count the number of cycles (simple cycles) in this modified graph. A cycle is defined as follows: choose an arbitrary vertex as the starting point, traverse along distinct edges through distinct vertices, and finally return to the starting vertex. Note that each cycle must contain at least 3 vertices. The answer can be very large, so output it modulo \(998244353\).

Definition: A cycle is a closed path that starts and ends at the same vertex, and in which no edge and no vertex (except the starting/ending vertex) is repeated.

Reminder: In the complete graph on n vertices, the total number of cycles is normally computed by summing over all possible cycle lengths from 3 to n. In our problem, because one edge is removed, you should subtract out the cycles that used the removed edge.

inputFormat

The input consists of a single integer n (\(n \ge 1\)).

outputFormat

Output a single integer representing the number of cycles in the graph after the removal of one edge, modulo \(998244353\).

sample

2

0