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