Background

In order to enjoy a pleasant life in the underworld rather than being condemned to hell, humans have abandoned the practice of taking their own lives and are striving to live fully. In this light, humans seem somewhat positive and endearing. (Sagemoto Aya)

The linear creature moves unidirectionally towards the underworld along a one-dimensional staircase.

Originally, it would only need to take $n$ steps to reach Hakurei Shrine by moving one step at a time.

However, Cirno found this too monotonous, so the one-dimensional barrier was broken, and the linear path sprouted into a cauliflower-like branching structure.

Problem Description

The linear creature needs to move from the $1$st step to the $(n+1)$th step.

Initially, each step from $1$ to $n$ has a directed edge leading to the next step, $i \rightarrow i+1$.

Then, Cirno added $m$ ancestral edges $u_i \rightarrow v_i (u_i \ge v_i)$, forming an ancestral graph.

Each step, the linear creature will equally likely choose an outgoing edge from the current step and move to the corresponding step.

When it reaches the $(n+1)$th step, the linear creature stops moving.

Cirno also counts the total number of steps taken by the linear creature, denoted as $\delta$.

Cirno wants to know the mathematical expectation of $\delta$, denoted as $E(\delta)$, modulo $998244353$.

Input Format

The first line contains three integers $id$, $n$, and $m$.

The following $m$ lines each contain two integers $u_i$ and $v_i$.

$id$ represents the subtask number, and other variables have the same meanings as described above.

Output Format

One line containing an integer $E(\delta)$, with the same meanings as described above.

Sample Input and Output

Input Sample #1

1 5 5
1 1
2 2
3 3
4 4
5 5

Output Sample #1

10

Input Sample #2

2 5 5
1 1
2 1
3 2
4 3
5 4

Output Sample #2

30

Input Sample #3

3 5 5
1 1
2 1
3 1
4 1
5 1

Output Sample #3

62

Input Sample #4

4 5 5
1 1
3 1
4 2
5 1
5 5

Output Sample #4

35

Notes

Posterior Mathematical Knowledge

• Power Series Summation: If $x > 1$, then $\sum\limits_{i=1}^{\infty}\big(\frac{1}{x}\big)^i = \frac{1}{x} + \frac{1}{x^2} + \frac{1}{x^3} + \cdots = \frac{1}{x-1}$.
• Mathematical Expectation: The sum of the products of each possible outcome's probability and its value, reflecting the average value of the random variable.
• Discrete Expectation Formula: $E(x) = \sum\limits_{k=1}^{\infty} x_k p_k$.

Data Range and Constraints

For $100\%$ of the data, it is guaranteed that: $\in \{1,2,3,4,5\}$, $0 < n, m \le 10^6$, $1 \le v_i \le u_i \le n$.

Subtasks (Bundled Testing)

• Subtask1 ($10\%$): The ancestral graph has self-loops at all points and all edges are self-loops (not drawn), forming a structure like:
  

• Subtask2 ($10\%$): The ancestral graph has each point connected only to its predecessor, with the special case that node $1$ connects to itself, forming a structure like:
  

• Subtask3 ($10\%$): The ancestral graph has all points connected only to node $1$, forming a structure like:
  

• Subtask4 ($10\%$): $n \le 100$, $m \le 1000$.

• Subtask5 ($60\%$): No special restrictions.

Postscript

The title of the problem is derived from th17 Touhou Kikeijuu 6 Boss Haniyasushin Kana's Hard / Lunatic difficulty spell card Linear "Linear Creature".

见题面 Input 部分

见题面 Output 部分