一位来自之前莫斯科分区赛的线性代数老教授总是用海量的家庭作业折磨他的学生。他想出了一种比逐一列出所有元素更快的方法来描述一个巨大的对称方阵。

教授选择了一个正整数 $n$ 并给出了 $m$ 个区间 $[l_1, r_1], \dots, [l_m, r_m]$，其中对于所有的 $i = 1, \dots, m$，都有 $l_i$ 和 $r_i$ 为整数，且 $1 \le l_i \le r_i \le n$。$n \times n$ 的矩阵 $A$ 构造如下：对于任意一对下标 $x, y$，矩阵元素 $A_{x,y}$ 等于满足 $x$ 和 $y$ 同时属于区间 $[l_i, r_i]$ 的下标 $i$ ($1 \le i \le m$) 的个数。例如，当 $n = 3$ 且区间列表为 $[1, 2], [2, 3], [1, 2], [3, 3]$ 时，得到的矩阵 $A$ 为： $$ \begin{pmatrix} 2 & 2 & 0 \\ 2 & 3 & 1 \\ 0 & 1 & 2 \end{pmatrix} $$

给定 $n$ 和区间列表，教授要求学生计算所得矩阵 $A$ 的行列式。教授不在乎比较巨大的数字，所以他要求计算结果对他的最爱质数 $998\,244\,353$ 取模。

教授虽然严厉，但也是一位通情达理的老师：他认为如果写下题目本身比解决题目更难，那么练习就没有多大意义。因此，在他的作业中，$m$ 从来不会比 $n$ 大太多，更准确地说，$m \le n + 300$。

在教授的课上待了几个学期后，你对他这种态度感到厌烦，决定写一个程序来为你计算答案。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500\,000, m \le n + 300$)。

接下来的 $m$ 行描述了教授给出的区间。第 $i$ 行包含两个整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)。

输出格式

输出一个整数——矩阵 $A$ 的行列式对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3 4
1 2
2 3
1 2
3 3

样例输出 1

2