광부
시간 제한1초메모리 제한256 MB
n개의 구간과 m개의 점이 주어질 때, 교집합이 주어진 점 중 하나 이상을 포함하는 공집합이 아닌 구간 부분집합의 개수를 998244353으로 나눈 나머지로 구한다.
문제
광산에는 서로 다른 종류의 광물이 있다. 광산은 좌표축으로 나타낼 수 있고, 번째 광물은 구간 안의 어느 위치에서든 캘 수 있다.
당신은 이 광산에서 일하는 광부이다. 매일 감독관은 광물을 캐는 작업을 하나씩 준다. 작업은 서로 다른 광물로 이루어진 공집합이 아닌 집합이며(모두 가지가 있다), 목표는 그 집합에 들어 있는 광물을 전부 모으는 것이다.
광산에는 개의 안전한 위치 가 있다. 어떤 작업이 쉬운 작업이라는 것은, 안전한 위치 를 하나 골라 그곳에서 필요한 광물을 모두 캘 수 있다는 뜻이다.
이제 쉬운 작업의 개수를 세려고 한다.
입력
첫째 줄에 두 정수 과 이 주어진다().
그다음 개의 줄이 주어지고, 각 줄에는 두 정수 와 가 있다().
그다음 개의 줄이 주어지고, 각 줄에는 정수 가 하나씩 있다().
출력
쉬운 작업의 개수를 으로 나눈 나머지를 한 줄에 출력한다.