Риби
У казках Шахерезади розповідається, що далеко в центрі пустелі є озеро. Спочатку в озері було 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 не має ніякого іншого змісту, крім як для спрощення обчислень.