34943번 - 대충 그래프 개수 세는 문제

문제

구간 그래프(Interval Graph)란, 각 정점을 수직선 상의 구간으로 표현할 수 있는 그래프를 의미한다. 구체적으로, 그래프 $G = (V, E)$가 구간 그래프라는 것은, 각 정점 $v \in V$에 대응하는 수직선 상의 구간 $I_v = [s_v, e_v]$가 존재하여, 두 정점 $u, v$ 사이에 간선이 존재할 필요충분조건이 $I_u \cap I_v \ne \emptyset$인 경우를 의미한다.

그래프 $G = (V, E)$와 정점 부분집합 $S \subseteq V$가 주어질 때, $S$에 의해 유도된 부분그래프(Induced Subgraph) $G[S]$는 다음과 같이 정의된다.

• 정점 집합: $S$
• 간선 집합: $\left\{(u, v) \in E \mid u,v \in S\right\}$.

다시 말해, $S$에 속한 정점과, $S$에 속한 두 정점을 연결하는 간선만을 모두 이용해 만든 그래프를 의미한다.

구간 그래프 $G = (V, E)$의 각 정점에 대응되는 $N$개의 구간 $I_1, I_2, \cdots, I_N$이 주어진다.

$V$의 공집합이 아닌 부분집합 $S$에서 유도되는 부분그래프 $G[S]$가 연결 그래프가 되는 $S$의 개수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 구간의 개수 $N$이 주어진다. (2ドル \le N \le 250,000円$)

둘째 줄부터 $N$개의 줄에 걸쳐 구간의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번 구간의 양 끝점을 의미하는 두 정수 $s_i,ドル $e_i$가 공백으로 구분되어 주어진다. (1ドル \le s_i \le e_i \le 2N,ドル $s_1,s_2,\cdots,s_N,e_1,e_2,\cdots,e_N$은 모두 서로 다르다.)

입력으로 주어지는 수는 모두 정수이다.

출력

$G$의 정점 집합의 공집합이 아닌 부분집합 $S$에서 유도되는 부분그래프 $G[S]$가 연결 그래프가 되는 $S$의 개수를 998ドル,244円,353円$으로 나눈 나머지를 출력한다.

제한

노트