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){
		rep(j,n)D[i][j+1]+=D[i][j];
		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;
		}
		rep(j,n)D[i+1][j+1]+=D[i+1][j];
	}
	wt(D[k][n]);
}