Expected Path Length in a Directed Acyclic Graph

B city can be regarded as a directed acyclic graph (DAG) with \(n\) nodes and \(m\) edges. The graph may contain multiple edges. zbw randomly walks in B city. He chooses a path uniformly at random from all possible paths, where a path is defined as a sequence of vertices connected by directed edges, and the starting and ending nodes of a path may be the same (thus, a trivial path with 0 edges is allowed).

The length of a path is defined as the number of edges it contains. Your task is to compute the expected length of the path chosen by zbw. Since the answer can be a rational number, output it modulo \(998244353\) (i.e. if the answer is \(E= \frac{P}{Q}\), output \(P \cdot Q^{-1}\) mod \(998244353\)).

Formally, if \(S\) denotes the set of all paths (including trivial paths) in the graph, then you need to compute \[ E = \frac{\sum_{\pi \in S} \text{length}(\pi)}{|S|}, \] and output \(E\) modulo \(998244353\).

inputFormat

The input consists of:

• The first line contains two integers \(n\) and \(m\) (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 10^5\)), representing the number of nodes and the number of edges respectively.
• The following \(m\) lines each contain two integers \(u\) and \(v\) (\(1 \leq u, v \leq n\)), indicating a directed edge from node \(u\) to node \(v\). It is guaranteed that the graph is acyclic. Note: there may be multiple edges from \(u\) to \(v\).

outputFormat

Output a single integer, which is the expected length of the path chosen by zbw modulo \(998244353\). In other words, if the expected value is \(\frac{P}{Q}\), output \(P \cdot Q^{-1} \bmod 998244353\).

sample

3 0

0