F. Primeiras chamadas

Time limit: 5000 msMemory limit: 256 MB

Há $n$ participantes em uma fila, nas posições de $1$ a $n$ , e $m$ comissões. A comissão $j$ acompanha os participantes nas posições de $l_j$ até $r_j$ , inclusive.

Os participantes serão chamados em uma ordem escolhida uniformemente entre todas as $n!$ permutações. Cada comissão seleciona o primeiro participante chamado entre aqueles que acompanha. Um mesmo participante pode ser selecionado por várias comissões.

Determine o valor esperado do número de participantes distintos selecionados por pelo menos uma comissão. Imprima esse valor módulo $998244353$ : se a esperança for a fração $A/B$ com $B$ não divisível pelo módulo, imprima $A\cdot B^{-1}$ módulo .

Input

A primeira linha contém $n$ e $m$ ( $1\le n\le 200000$ , $1\le m\le 5000$ ). Cada uma das próximas linhas contém e (). Comissões com o mesmo intervalo são permitidas.

Output

Imprima a esperança pedida módulo $998244353$ .

Samples

Sample 1

Input

3 2
1 2
2 3

Output

665496237

Se o participante 2 for chamado primeiro, só ele será escolhido. Nos outros casos, serão escolhidos dois participantes distintos. A esperança é $5/3$ , representada por 665496237 módulo $998244353$ .

Sample 2

Input

4 2
1 4
1 4

Output

As duas comissões sempre selecionam a mesma pessoa.

Sample 3

Input

Output

Cada comissão acompanha uma única pessoa; as três pessoas são sempre selecionadas.