구간 색칠 복잡도 timer 2s memory 1024MB

초등학교 앞에는 일직선 모양의 긴 산책로가 있다. 이 산책로 위에는 눈에 보이지 않는 칸들이 1, 2, 3, … 순서대로 일렬로 놓여 있다고 생각하자.

민지는 이 산책로 위에 구간 N개를 표시해 두었다. 각 구간은 두 정수 l_i, r_i​로 주어지며, 이 구간은 l_i 이상 r_i​ 이하에 있는 모든 점을 덮고 있다고 생각한다. (즉, 구간 [l_i, r_i]는 l_i \le x \le r_i​ 를 만족하는 모든 점 x를 포함한다.)

민지는 이 구간들을 가지고 다음과 같은 놀이를 하려고 한다.

민지는 준비해 둔 N개의 구간 중에서 원하는 것들을 골라서 사용할 수 있다.

• 아무 구간도 고르지 않는 경우(공집합)도 있다.

• 한 개만 고를 수도 있고,

• 여러 개를 동시에 고를 수도 있으며,

• 모든 구간을 다 고를 수도 있다.

이렇게 구간을 고르는 방법은 총 2^N가지가 있다.

어떤 방법으로 구간들을 골랐을 때, 선택한 구간들이 덮고 있는 모든 부분을 색칠된 구간이라고 하자. (여러 구간이 겹쳐도, 그 부분은 한 번만 색칠된 것으로 본다.)

색칠된 부분을 왼쪽부터 오른쪽으로 보았을 때, 끊기지 않고 쭉 이어져 있는 색칠된 부분 하나를
색칠된 구간의 한 “조각”이라고 부르자.

예를 들어,

• 색칠된 부분이 [1, 5] 한 덩어리라면 조각 수는 1개이다.

• 색칠된 부분이 [1, 2]와 [4, 5]처럼 떨어진 두 덩어리라면 조각 수는 2개이다.

어떤 구간 집합을 골랐을 때 색칠된 조각의 개수를 c라고 하자. 구간을 하나도 고르지 않으면 색칠된 부분이 없으므로 c = 0이다.

정수 K가 하나 주어져 있다. 민지는, 구간을 한 가지 방법으로 골랐을 때의 복잡도를 다음과 같이 정의한다: \text{복잡도} = c^K

여기서 c는 그때 색칠된 조각의 개수이다.

• 조각이 0개이면 복잡도는 0^K = 0,

• 조각이 1개이면 복잡도는 1^K = 1,

• 조각이 2개이면 복잡도는 2^K,

• 조각이 3개이면 복잡도는 3^K, … 와 같다.

민지는 가능한 모든 구간 고르는 방법 2^N가지에 대해, 각각의 복잡도를 모두 더한 값이 궁금하다.

이 값이 너무 클 수 있으므로, 그 합을 1\,000\,000\,007 (10^9 + 7)로 나눈 나머지를 구해 출력하자.