mint*p,*q,D[4d3][4d3],W;ll L[3d4],R[3d4],n,m,k;{rd(n,m,k,(L,R)(m));1[p=*D]=1;rep(i,k){p[1..n]+=p[0..];rep(j,m)L[j][q=D[i+1]]+=W=p[R[j]]-p[L[j]-1],q[R[j]+1]-=W;q[1..n]+=q[0..];p=q;}wt(p[n]);}