A13681 | No Game No Life

Let's consider the following game of Alice and Bob on a directed acyclic graph. Each vertex may contain an arbitrary number of chips. Alice and Bob make turns alternating. Alice goes first. In one turn player can move exactly one chip along any edge outgoing from the vertex that contains this chip to the end of this edge. The one who cannot make a turn loses. Both players play optimally.

Consider the following process that takes place every second on a given graph with $n$ vertices:

1. An integer $v$ is chosen equiprobably from $[1, n + 1]$ .
2. If $v \leq n$ , we add a chip to the $v$ -th vertex and go back to step 1.
3. If $v = n + 1$ , Alice and Bob play the game with the current arrangement of chips and the winner is determined. After that, the process is terminated.

Find the probability that Alice will win the game. It can be shown that the answer can be represented as $\frac{P}{Q}$ , where $P$ and $Q$ are coprime integers and $Q \not\equiv 0 \pmod{998\,244\,353}$ . Print the value of $P \cdot Q^{-1} \bmod 998\,244\,353$ .

The first line contains two integers $n$ and $m$ — the number of vertices and edges of the graph ( $1 \leq n \leq 10^5$ , $0 \leq m \leq 10^5$ ).

The following $m$ lines contain edges description. The $i$ -th of them contains two integers $u_i$ and $v_i$ — the beginning and the end vertices of the $i$ -th edge ( $1 \leq u_i, v_i \leq n$ ). It's guaranteed that the graph is acyclic.

Output a single integer — the probability of Alice victory modulo $998\,244\,353$ .