Expected Steps in a Retrograde Graph

A linear creature starts at step \(1\) and needs to reach step \(n+1\). Initially, for each \(1 \le i \le n\) there is a directed edge from step \(i\) to step \(i+1\). After that, Cirno adds \(m\) extra retrograde edges; each extra edge is given as \(u_i \rightarrow v_i\) with \(1 \le v_i \le u_i \le n\). These extra edges form a retrograde graph.

The creature moves in discrete steps. At any step, if it is at some step \(i (1 \le i \le n)\), it chooses one of the outgoing edges uniformly at random and follows it. Note that if an edge leads to step \(n+1\), the creature stops immediately. Let \(\delta\) be the total number of steps taken. Your task is to compute the expected value \(E(\delta)\), and output the result modulo \(998244353\).

Hint: If a node has \(d\) outgoing edges and among them there are some self–loops (i.e. edges from \(i\) to \(i\)), then the expectation \(f[i]\) satisfies \[ d \cdot f[i] = d + [\text{(number of non-self loop edges)}] \text{ terms} + [\text{self–loops which contribute } f[i]]. \] After rearranging, the equation for node \(i\) becomes \[ (d - c_i) \cdot f[i] - \sum_{\substack{j\;:\;j\neq i\\j\in out(i)}} f[j] = d,\] where \(c_i\) is the count of self–loops at node \(i\) and \(out(i)\) is the list of neighbors (ignoring edges to \(n+1\) since \(f[n+1]=0\)). This yields a system of \(n\) linear equations with \(n\) unknowns. Solve it modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n \le 500,\ 0 \le m \le 500)\) representing the number of basic steps and the number of retrograde edges.

Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) \((1 \le v_i \le u_i \le n)\) denoting an extra retrograde edge from step \(u_i\) to step \(v_i\).

outputFormat

Output a single integer: the expected number of steps \(E(\delta)\) modulo \(998244353\).

sample

3 1
2 1

13