물고기

사막 한가운데 멀리 호수가 하나 있다. 이 호수에는 원래 물고기 $F$마리가 살고 있었다. 지구에서 가장 값진 보석 중 서로 다른 $K$종류가 선택되었고, $F$마리의 각 물고기는 정확히 한 개의 보석을 삼켰다. $K$가 $F$보다 작을 수 있으므로, 여러 물고기가 같은 종류의 보석을 삼켰을 수도 있다.

시간이 흐르면서 일부 물고기는 다른 물고기를 잡아먹었다. 물고기 $A$는 자신의 길이가 물고기 $B$의 두 배 이상일 때, 즉 $L_A \ge 2 \cdot L_B$일 때에만 $B$를 잡아먹을 수 있다. 언제 잡아먹을지에 대한 규칙은 없다. 한 물고기가 더 작은 물고기 여러 마리를 잇달아 잡아먹을 수도 있고, 잡아먹을 수 있더라도 한 마리도 먹지 않을 수도 있다. 물고기가 더 작은 물고기를 먹어도 자신의 길이는 변하지 않으며, 먹힌 물고기의 뱃속에 있던 보석은 모두 손상 없이 잡아먹은 물고기의 뱃속으로 옮겨진다.

당신은 호수에서 물고기 한 마리를 꺼내어 그 뱃속에 들어 있는 보석을 모두 가질 수 있다. 길을 나서기 전에, 물고기 한 마리를 잡아서 얻을 수 있는 서로 다른 보석 조합이 몇 가지인지 알고 싶다.

각 물고기의 길이와 처음에 삼킨 보석의 종류가 주어졌을 때, 어떤 물고기의 뱃속에 최종적으로 들어 있을 수 있는 서로 다른 보석 조합의 수를 주어진 정수 $M$으로 나눈 나머지를 구하는 프로그램을 작성하라. 하나의 조합은 오직 $K$종류의 보석을 각각 몇 개씩 포함하는지에 의해서만 결정된다. 보석 사이에 순서는 없으며, 같은 종류의 보석 두 개는 서로 구별되지 않는다.

• 첫째 줄에 호수에 원래 있던 물고기의 수 $F$가 주어진다 ($1 \le F \le 500{,}000$).
• 둘째 줄에 보석의 종류 수 $K$가 주어진다. 보석의 종류는 $1$부터 $K$까지의 번호로 나타낸다 ($1 \le K \le F$).
• 셋째 줄에 정수 $M$이 주어진다 ($2 \le M \le 30{,}000$).
• 다음 $F$개의 각 줄에는 한 물고기를 나타내는 두 정수가 공백으로 구분되어 주어진다. 각각 물고기의 길이와 그 물고기가 처음에 삼킨 보석의 종류이다 ($1 \le L_X \le 1{,}000{,}000{,}000$).

$K$종류의 보석이 각각 적어도 하나씩은 존재함이 보장된다.

$0$ 이상 $M-1$ 이하의 정수 하나를 한 줄에 출력한다. 이는 가능한 서로 다른 보석 조합의 수를 $M$으로 나눈 나머지이다. $M$은 계산 결과를 작게 유지하는 것 외에 다른 의미는 없다.