#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define pb push_back const int N=5e5+5,MAXA=1e6+5,inf=1e9,MOD=1e9+7; pair<int,int> fsh[N]; vector<int> pos[N]; /* * take stuff not seen * in that case have segtree0 which consists of how many ways and remove all occurences of type x after u finish calculating it * take stuff seen but cant eat u in that case update all type x in segtree1 to 1 and calculate how many ways (basically taking all type x) */ int seg[N*4],offset=1,m; void update(int idx,int val){ idx+=offset; seg[idx]+=val; idx/=2; while(idx>0){ seg[idx]=seg[idx*2]*seg[idx*2+1]%m; idx/=2; } } int query(int node,int qlo,int qhi,int lo,int hi){ if(lo>=qlo && hi<=qhi)return seg[node]; if(lo>qhi || hi<qlo)return 1; int mid=(lo+hi)/2; return query(node*2,qlo,qhi,lo,mid)*query(node*2+1,qlo,qhi,mid+1,hi)%m; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int f,k; cin>>f>>k>>m; //m=1e9; for(int i=0;i<N*4;i++)seg[i]=1; while(offset<=f)offset*=2; for(int i=1;i<=f;i++)cin>>fsh[i].first>>fsh[i].second; sort(fsh+1,fsh+f+1); for(int i=1;i<=f;i++)pos[fsh[i].second].pb(i); for(int i=1;i<=f;i++)update(pos[fsh[i].second].back(),1); int in=f,ans=0; for(int i=f;i>=1;i--){ int length=fsh[i].first,color=fsh[i].second; if(pos[color].back()!=i)continue; // cout<<in<<endl; if(in<i)update(i,1); while(in>0 && fsh[in].first*2>length){ if(in!=i)update(pos[fsh[in].second].back(),-1); in--; } int cur=pos[color].size()-1; while(cur>0 && length<2*fsh[pos[color][cur]].first)cur--; if(length>=2*fsh[pos[color][cur]].first)cur++; int l=i,r=f; while(l<r){ int mid=(l+r+1)/2; if(fsh[mid].first>=fsh[pos[color][cur]].first*2)r=mid-1; else l=mid; } int og=seg[i+offset]; update(i,-2); //remove case of choosing maximum and nothing ans+=query(1,1,i,0,offset-1); // cout<<ans<<' '; update(i,1-seg[i+offset]); //forcing to choose maximum // cout<<seg[4+offset]<<'s'<<endl; ans+=query(1,1,r,0,offset-1); update(i,og-2); //resetting it to old value but removing i ans%=m; // cout<<ans<<endl; } cout<<ans; }