อัญมณีในท้องปลา: อย่าหักลบทีหลัง ให้ตั้งกฎว่าคำตอบเป็นของใครตั้งแต่แรก

// เฉลยชุดทดสอบย่อย K ไม่เกิน 7,000 (70 คะแนน)
// สูตรเดียวกับเฉลยเต็ม ต่างแค่ไม่ยกเซกเมนต์ทรีมาใช้ คูณไล่เอาตรง ๆ เป็น O(K^2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int F, K; ll MOD;
    scanf("%d %d %lld", &F, &K, &MOD);
    vector<int> L(F), T(F);
    vector<vector<int>> byType(K + 1);
    for (int i = 0; i < F; i++) { scanf("%d %d", &L[i], &T[i]); byType[T[i]].push_back(L[i]); }
    for (int t = 1; t <= K; t++) sort(byType[t].begin(), byType[t].end());

    vector<int> ord(K); for (int t = 1; t <= K; t++) ord[t - 1] = t;
    sort(ord.begin(), ord.end(), [&](int a, int b) { return byType[a].back() < byType[b].back(); });
    vector<int> posOf(K + 1); vector<ll> B(K);
    for (int i = 0; i < K; i++) { posOf[ord[i]] = i; B[i] = byType[ord[i]].back(); }

    vector<pair<int,int>> fish(F);
    for (int i = 0; i < F; i++) fish[i] = {L[i], T[i]};
    sort(fish.begin(), fish.end());

    vector<ll> m(K, 0), val(K, 1 % MOD);        // val[p] = m[p] + 1 คือจำนวนทางเลือกของชนิดนั้น
    int ptr = 0; ll ans = 0;
    for (int i = 0; i < K; i++) {
        while (ptr < F && 2LL * fish[ptr].first <= B[i]) {
            int p = posOf[fish[ptr].second]; m[p]++; val[p] = (m[p] + 1) % MOD; ptr++;
        }
        ll left = 1 % MOD;
        for (int j = 0; j < i; j++) left = left * val[j] % MOD;     // คูณไล่แทนการถามเซกเมนต์ทรี
        ans = (ans + m[i] % MOD * left) % MOD;

        const vector<int>& v = byType[ord[i]];
        int xi = (int)(lower_bound(v.begin(), v.end(), B[i] / 2 + 1) - v.begin());
        int J = (int)(lower_bound(B.begin(), B.end(), 2LL * v[xi]) - B.begin());
        if (J < i + 1) J = i + 1;
        ll mid = 1 % MOD;
        for (int j = i + 1; j < J; j++) mid = mid * val[j] % MOD;
        ans = (ans + left * mid) % MOD;
    }
    printf("%lld\n", ans % MOD);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int SZ; ll MOD; vector<ll> seg;                 // เซกเมนต์ทรีเก็บ "ผลคูณ" เพราะ M ไม่ใช่จำนวนเฉพาะ จึงหารกลับไม่ได้
void build(int k){ SZ=1; while(SZ<k) SZ<<=1; seg.assign(2*SZ,1%MOD); }
void setv(int p,ll v){ p+=SZ; seg[p]=v%MOD; for(p>>=1;p;p>>=1) seg[p]=seg[2*p]*seg[2*p+1]%MOD; }
ll prod(int l,int r){ if(l>r) return 1%MOD; ll a=1%MOD,b=1%MOD; for(l+=SZ,r+=SZ+1;l<r;l>>=1,r>>=1){ if(l&1) a=a*seg[l++]%MOD; if(r&1) b=seg[--r]*b%MOD; } return a*b%MOD; }
int main(){
    int F,K; if(scanf("%d %d %lld",&F,&K,&MOD)!=3) return 0;
    vector<int> L(F),T(F);
    vector<vector<int>> byType(K+1);
    for(int i=0;i<F;i++){ scanf("%d %d",&L[i],&T[i]); byType[T[i]].push_back(L[i]); }
    for(int t=1;t<=K;t++) sort(byType[t].begin(),byType[t].end());
    vector<int> ord; ord.reserve(K);
    for(int t=1;t<=K;t++) ord.push_back(t);
    sort(ord.begin(),ord.end(),[&](int a,int b){ return byType[a].back()<byType[b].back(); });
    vector<int> posOf(K+1); vector<ll> B(K);
    for(int i=0;i<K;i++){ posOf[ord[i]]=i; B[i]=byType[ord[i]].back(); }

    vector<pair<int,int>> fish(F);               // (ความยาว, ชนิด) เรียงตามความยาว
    for(int i=0;i<F;i++) fish[i]={L[i],T[i]};
    sort(fish.begin(),fish.end());

    build(K);
    vector<ll> m(K,0);                           // m[p] = จำนวนปลาชนิด ord[p] ที่อยู่ในคำนำหน้าปัจจุบัน
    int ptr=0; ll ans=0;
    for(int i=0;i<K;i++){
        while(ptr<F && 2LL*fish[ptr].first<=B[i]){ int p=posOf[fish[ptr].second]; m[p]++; setv(p,(m[p]+1)%MOD); ptr++; }
        ll own=m[i];
        ll left=prod(0,i-1);
        ans=(ans+own%MOD*left)%MOD;              // กรณี (ข) นับชนิดตัวเองไม่เต็มเพดาน
        // กรณี (ก) นับชนิดตัวเองเต็มเพดาน  ต้องหา J = ชนิดแรกที่คำนำหน้ากลืนปลาตัว X เข้าไปได้
        const vector<int>& v=byType[ord[i]];
        ll bt=B[i];
        int xi=(int)(lower_bound(v.begin(),v.end(),bt/2+1)-v.begin());   // ตัวแรกที่ 2L > bt
        ll need=2LL*v[xi];
        int J=(int)(lower_bound(B.begin(),B.end(),need)-B.begin());
        if(J<i+1) J=i+1;
        ans=(ans+left*prod(i+1,J-1))%MOD;
    }
    printf("%lld\n",ans%MOD);
}