Рыбы
В сказаниях Шахерезады говорится, что далеко в центре пустыни есть озеро. Изначально в озере было F рыб. Из лучших самоцветов Земли были отобраны K различных видов, и получилось так, что каждая из F рыб проглотила ровно один самоцвет какого-то вида. Поскольку K могло быть меньше чем F, две или более рыбы могли проглотить самоцветы одного вида.
Со временем некоторые рыбы съели других рыб. Одна рыба могла съесть другую рыбу только в том случае, если ее длина хотя бы в два раза больше (рыба A могла съесть рыбу B только в том случае, если LA >= 2 * LB). Нет правил, по которым одна рыба решает съесть других рыб. Рыба могла решить съесть некоторое количество меньших рыб, в то же время некоторые рыбы могли решить не есть других рыб, несмотря на то, что они могли бы это сделать. Когда рыба съедала меньшую рыбу, ее длина не изменялась, но все самоцветы из желудка меньшей рыбы попадали неповрежденными в желудок большей рыбы.
В сказаниях Шахерезады говорится, что если найти это озеро, то можно поймать ровно одну рыбу и забрать все самоцветы из ее желудка. Вы, конечно, желаете попытать счастья, но прежде, чем вы отправитесь в путешествие, вам необходимо узнать, какое количество различных комбинаций самоцветов вы можете получить, поймав одну единственную рыбу.
Напишите программу, которая по длине каждой рыбы и виду изначально проглоченного каждой рыбой самоцвета определяет количество различных комбинаций самоцветов, которые могут находиться в желудке какой-либо рыбы, по модулю заданного целого числа M. Комбинация определяется только количеством самоцветов каждого из K видов. Не существует понятия порядка среди самоцветов, и два самоцвета одного вида неразличимы.
1 <= F <= 500 000 (F – изначальное количество рыб в озере) 1 <= K <= F (K – количество различных видов самоцветов) 2 <= M <= 30 000 1 <= LX <= 1 000 000 000 (LX – длина рыбы X)
Входные данные
Ваша програма должна читать из стандартного ввода следующие данные:
Строка 1 содержит целое число F – изначальное количество рыб в озере.
Строка 2 содержит целое число K – количество различных видов самоцветов. Виды самоцветов представляются числами от 1 до K включительно.
Строка 3 содержит целое число M.
Каждая из следующих F строк описывает одну рыбу, используя 2 целых числа, разделенные одним пробелом: длину рыбы и тип самоцвета, изначально проглоченного этой рыбой.
Замечание. Во всех тестах, используемых для оценки решения, гарантируется, что существует хотя бы один самоцвет каждого из K видов.
Выходные данные
Ваша программа должна вывести в стандартный вывод единственную строку, содержащую одно целое число в пределах от 0 до (M-1) включительно – количество различных возможных комбинаций самоцветов по модулю числа M.
Следует заметить, что для решения задачи значение числа M не имеет никакого другого смысла, кроме как упрощения вычислений.