Para una permutación de $1, 2, \ldots, n$, sea $s_i$ la longitud del subarreglo contiguo más corto que contiene todos los valores $1, 2, \ldots, i$.

Sea $\operatorname{pos}_p(x)$ la posición de $x$ en la permutación; se cumple que

$$ s_i = \max_{1 \le x \le i} \operatorname{pos}_p(x) - \min_{1 \le x \le i} \operatorname{pos}_p(x) + 1. $$

Para cada $i$, se da una restricción en forma de intervalo $[l_i, r_i]$.

Cuenta las permutaciones que satisfacen $l_i \le s_i \le r_i$ para todo $i$. Imprime la respuesta módulo $998244353$.

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 2 \cdot 10^5$).

Cada una de las siguientes $n$ líneas contiene dos enteros $l_i$ y $r_i$ ($1 \le l_i \le r_i \le n$).

Salida

Imprime el número de permutaciones válidas módulo $998244353$.

Ten en cuenta que puede no existir ninguna permutación válida.

Ejemplos

Entrada 1

3
1 1
2 2
3 3

Salida 1

4

Nota

Las permutaciones válidas del ejemplo son $(1, 2, 3)$, $(2, 1, 3)$, $(3, 1, 2)$ y $(3, 2, 1)$.