전력

바이텔론 마을 주민들은 풍력으로 집에 전기를 공급하기로 하고 풍차를 일렬로 세웠습니다.

마을을 가로지르는 도로는 하나뿐입니다. 모든 집은 도로 한쪽에 일직선으로 늘어서 있고, 풍차는 반대쪽에 일직선으로 늘어서 있습니다. 일부 풍차와 일부 집은 도로 위를 지나는 고압선으로 연결되어 있습니다. 풍차 하나가 여러 집과 연결될 수도, 집 하나가 여러 풍차와 연결될 수도 있으며, 아무것과도 연결되지 않은 풍차나 집이 있을 수도 있습니다. 모든 고압선은 직선 구간이고, 어떤 (집, 풍차) 쌍에도 고압선은 많아야 하나만 존재합니다.

정부는 더 깔끔한 배치를 원합니다. 기존 고압선 중 일부만 남겨 다음 두 조건을 모두 만족시키려 합니다.

• 각 풍차는 많아야 한 집에만 전기를 보내고, 각 집은 많아야 한 풍차에서만 전기를 받는다.
• 위에서 내려다볼 때 남긴 두 고압선이 서로 교차하지 않는다. (집과 풍차가 각각 평행하게 늘어서 있으므로 모든 고압선은 직선으로 보입니다. 두 고압선이 교차하면 바람에 밀려 맞닿아 합선이 날 수 있으므로 교차는 허용되지 않습니다.)

기존 고압선의 부분집합 중 두 조건을 모두 만족하는 것이 몇 가지인지 세십시오. 고압선을 하나도 남기지 않는 빈 부분집합도 유효한 배치 하나로 셉니다.

경우의 수가 매우 커질 수 있으므로, 정부가 정한 수 $r$로 나눈 나머지를 출력하십시오.

표준 입력에서 기존 고압선의 정보를 읽어, 조건을 만족하는 부분집합의 개수를 $r$로 나눈 나머지를 표준 출력에 쓰는 프로그램을 작성하십시오.

첫 줄에 정수 네 개 $n$, $m$, $k$, $r$이 공백 하나로 구분되어 주어집니다.

• $1 \le n, m \le 200\,000$: 집의 수와 풍차의 수. 집은 도로를 따라 놓인 순서대로 $1$번부터 $n$번까지, 풍차는 반대쪽에 같은 방향으로 $1$번부터 $m$번까지 번호가 매겨져 있습니다.
• $1 \le k \le 1\,000\,000$: 기존 고압선의 수.
• $2 \le r \le 10^9$: 정부가 정한 나눗셈의 제수.

이어지는 $k$개의 줄 중 $i$번째 줄에는 정수 $h_i$와 $w_i$가 주어지며($1 \le h_i \le n$, $1 \le w_i \le m$), 이는 $i$번째 고압선이 집 $h_i$와 풍차 $w_i$를 잇는다는 뜻입니다. 같은 (집, 풍차) 쌍은 두 번 이상 나타나지 않습니다.

조건을 만족하는 고압선 부분집합의 개수를 $r$로 나눈 나머지를 한 줄에 정수 하나로 출력하십시오.

그림의 배치에서는 고압선을 하나도 남기지 않는 방법이 $1$가지, 한 개만 남기는 방법이 $5$가지, 두 개를 남기는 방법이 $2$가지, 세 개를 남기는 방법은 없으므로, 모두 합해 $8$가지입니다.

남긴 두 고압선은, 한쪽이 번호가 더 작은 집에서 출발하면서 번호가 더 큰 풍차에 도착할 때 정확히 교차합니다. 따라서 유효한 부분집합이란 집 번호와 풍차 번호가 함께 증가하는 고압선들의 모임입니다.