Задача №1891. Рыбки
Как рассказывала Шахерезада, в одной далёкой стране, посреди пустыни, есть озеро. Вначале в том озере было \(F\) рыбок. Были выбраны \(K\) ценнейших видов драгоценных камней, и каждая рыбка проглотила один камень. Заметьте, что \(K\) может быть меньше \(F\), поэтому некоторым рыбкам достались камни одного вида.
Время шло, рыбки охотились друг на друга. Одна рыбка может съесть другую, если та хотя бы в два раза короче (рыбка \(A\) может съесть рыбку \(B\) тогда и только тогда, когда \(L_A \ge 2L_B\)). Рыбки выбирают своих жертв без каких-то особых правил. Одна рыбка может выбрать несколько меньших рыбок и съесть их одну за одной, а может и не съесть ни одной, даже если способна. Когда рыбка съедает другую, её длина не меняется, однако все камни из живота меньшей рыбки оказываются в животе большей.
Шахерезада рассказывала, что тот, кто сумеет отыскать озеро, получит право поймать одну рыбку оттуда и забрать все камни, оказавшиеся у неё в животе. Вы решили испытать удачу, но перед тем, как отправиться в путь, заинтересовались тем, сколько различных комбинаций камней можно получить, поймав одну рыбку.
Известно, камень какого вида проглотила каждая рыбка вначале. Вычислите количество комбинаций камней, которые можно получить, поймав ровно одну рыбку, по модулю \(M\). Комбинация однозначно определяется количеством камней каждого вида. Любые два камня одного вида неразличимы, порядок камней не имеет значения.
В первой строке записано единственное целое число \(F\) — начальное количество рыбок в озере (\(1 \le F \le 500\,000\)). Во второй строке записано единственное целое число \(K\) (\(1 \le K \le F\)) — количество видов драгоценных камней (пронумерованных целыми числами от \(1\) до \(K\)). В третьей строке записано единственное целое число \(M\) — модуль (\(2 \le M \le 30\,000\)). Каждая из следующих \(F\) строк содержит по два целых числа — длину соответствующей рыбки \(L_x\) и номер вида драгоценного камня \(G_x\), проглоченного ей (\(1 \le L_x \le 1\,000\,000\,000\), \(1 \le G_x \le K\)).
Гарантируется, что хотя бы один камень каждого вида от \(1\) до \(K\) проглочен хотя бы одной рыбкой.
Выведите единственное число — количество возможных комбинаций камней, взятое по модулю \(M\).
Всего 11 возможных комбинаций, поэтому нужно вывести 11 по модулю 7, то есть 4.
Возможные комбинации: \([1]\), \([1,2]\), \([1,2,3]\), \([1,2,3,3]\), \([1,3]\), \([1,3,3]\), \([2]\), \([2,3]\), \([2,3,3]\), \([3]\), и \([3,3]\). (Для каждой комбинации перечислены камни, её составляющие. К примеру, \([2,3,3]\) — комбинация, состоящая из одного камня вида 2 и двух камней вида 3.)
Эти комбинации можно получить следующими способами:
* \([1]\): Можно поймать вторую (или четвёртую) рыбку, пока она не съела какую-то ещё.
* \([1,2]\): Если вторая рыбка съест первую рыбку, в ней будут камень вида \(1\) (который она изначально проглотила), а также камень вида 2 (из первой рыбки).
* \([1,2,3]\): Один из возможных способов получения этой комбинации: четвёртая рыбка съедает первую, потом третья съедает четвёртую. Если теперь поймать третью рыбку, у неё в животе найдётся по одному камню всех видов.
* \([1,2,3,3]\): Четвёртая ест первую, третья ест четвёртую, третья ест пятую, вы ловите третью.
* \([1,3]\): Третья ест четвёртую, вы её ловите.
* \([1,3,3]\): Третья ест пятую, третья ест четвёртую, вы её ловите.
* \([2]\): Вы ловите первую рыбку.
* \([2,3]\): Третья ест первую, вы её ловите.
* \([2,3,3]\): Третья ест первую, третья ест пятую, вы её ловите.
* \([3]\): Вы ловите третью рыбку.
* \([3,3]\): Третья ест пятую, вы её ловите.
5 3 7 2 2 5 1 8 3 4 1 2 3
4