$1,2,\ldots,n$의 순열에 대해, $s_i$를 값 $1,2,\ldots,i$를 모두 포함하는 가장 짧은 연속 부분 배열의 길이라고 하자.

$\operatorname{pos}_p(x)$를 순열에서 $x$의 위치라고 하면 다음이 성립한다.

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

각 $i$에 대해 구간 제약 $[l_i,r_i]$가 주어진다.

모든 $i$에 대해 $l_i\le s_i\le r_i$를 만족하는 순열의 수를 구하여라. 답을 $998\,244\,353$으로 나눈 나머지를 출력하여라.

입력

첫 번째 줄에 정수 $n$이 주어진다（$1\le n\le2\cdot10^5$）.

다음 $n$개의 줄에는 각각 두 정수 $l_i$와 $r_i$가 주어진다（$1\le l_i\le r_i\le n$）.

출력

조건을 만족하는 순열의 수를 $998\,244\,353$으로 나눈 나머지를 출력하여라.

조건을 만족하는 순열이 존재하지 않을 수도 있다는 점에 유의하여라.

예제

입력 1

3
1 1
2 2
3 3

출력 1

4

참고

예제에서 조건을 만족하는 순열은 $(1,2,3)$, $(2,1,3)$, $(3,1,2)$, $(3,2,1)$이다.