#include typedef long long ll; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,a) FOR(i,0,a) using namespace std; const int MAX_N=3000,MAX_M=3000; const ll MOD=1e9+7; int N,M,K,L[MAX_M],R[MAX_M]; int n2; ll dp[MAX_N+1],laz[MAX_N<<2],psm[MAX_N+1]; void madd(ll &a,ll b){ a+=b; if(a>=MOD){ a-=MOD; } } void lazpro(int k,int a,int b){ if(laz[k]>0){ if(b-a>1){ madd(laz[(k<<1)+1],laz[k]); madd(laz[(k<<1)+2],laz[k]); } } } void add(int l,int r,ll x,int k,int a,int b){ if(r<=a || b<=l){ return; } if(l<=a && b<=r){ madd(laz[k],x); }else{ add(l,r,x,(k<<1)+1,a,(a+b)>>1); add(l,r,x,(k<<1)+2,(a+b)>>1,b); } } int main(){ scanf("%d %d %d",&N,&M,&K); REP(i,M){ scanf("%d %d",L+i,R+i); L[i]--; } n2=1; while(n2=MOD){ psm[j+1]-=MOD; } } memset(dp,0,sizeof(dp)); REP(j,M){ ll x=psm[R[j]]-psm[L[j]]; if(x<0){ x+=MOD; } dp[L[j]]+=x; dp[L[j]]%=MOD; dp[R[j]]+=MOD-x; dp[R[j]]%=MOD; } REP(j,N-1){ madd(dp[j+1],dp[j]); } } printf("%lld\n",dp[N-1]); }