longd3_function(ps, pss, pff, n,d)
{
#this program compute the probability P(N(n,d)=0)#
#i.e., the number of non-overlapping type 1 runs having at most 3 type 0# 
#under given initial ps and pf with length d is zero.d=#1+#0#
NN_(d^4-2*d^3+11*d^2+14*d+24)/24
pf_1-ps
psf_1-pss
pfs_1-pff
c0_matrix(0,1,NN-1)
p0_cbind(1,c0)
c1_matrix(1,NN-1,1)
U_rbind(c1,0)
M_matrix(0,NN,NN)
 for(ir in 0:(d-1)){
   for(jr in 0:ir){
     for(kr in 0:ir){
      for(lr in 0:ir){
for(ic in 0:(d-1)){
          for(jc in 0:ic){
             for(kc in 0:ic){
                for(lc in 0:ic){
if((kr>0 && kr<=jr)||(lr>0 && lr<=kr) ||
(jr==0 && ( kr!=0||lr!=0))|| (kr==0&&lr!=0)){rid_0}
           else{ rid_(ir^4-2*ir^3+11*ir^2+14*ir)/24+1+(jr-1+
(-6*ir^2-6*ir-6*ir*jr^2+6*ir^2*jr+12*ir*jr+2*jr^3-6*jr^2+4*jr)/12+1+
(((2*ir-jr-kr+2)*(kr-jr-1)/2)*(kr>jr)+1+(lr-kr)*(lr>kr))*(kr>1))*(jr>0)}
if((kc>0 && kc<=jc)||(lc>0 && lc<=kc) ||
(jc==0 && ( kc!=0||lc!=0))|| (kc==0&&lc!=0)){cid_0}
           else{ cid_(ic^4-2*ic^3+11*ic^2+14*ic)/24+1+(jc-1+
(-6*ic^2-6*ic-6*ic*jc^2+6*ic^2*jc+12*ic*jc+2*jc^3-6*jc^2+4*jc)/12+1+
(((2*ic-jc-kc+2)*(kc-jc-1)/2)*(kc>jc)+1+(lc-kc)*(lc>kc))*(kc>1))*(jc>0)}
if(jr!=1 && ir>0){
if(ic==ir+1 && kr==0 && jr==0 && kc==0 && jc==0){M[rid,cid]_pss}
if(ic==ir+1 && jc==(jr+1)*(jr>0)&&kc==(kr+1)*(kr>0)&&
lc==(lr+1)*(lr>0)){M[rid,cid]_pss}}
if(jr==1 && jc==1){
if(kr==0 && lr==0 && lc==0 && kc==2 && jc==1 && 
ic==ir+1){M[rid,cid]_pff}
if(ic==ir+1 && kc==2 && lc==kr+1 && lr==0 && kr>1){M[rid,cid]_pff}
if(lr>kr && kr>jr && ic==lr && kc==jr+1 && lc==kr+1){M[rid,cid]_pff}}
if(jr==1){
if(kr==0 && lr==0 && ic==ir+1 && jc==2 && kc==0 && 
lc==0){M[rid,cid]_pfs}
if(jc==2 && kc==kr+1 && ic==ir+1 && lc==0 && lr==0){M[rid,cid]_pfs}
if(ic==ir+1 && jc==jr+1 && kc==kr+1 && lc==lr+1 && lr>kr&& kr>jr)
{M[rid,cid]_pfs}}
if(ir>0 && jr!=1&& jc==1){
if(ic==ir+1){  
if( kr==0 && kc==0 && jr==0 && lr==0 && lc==0){M[rid,cid]_psf} 
if( jr>1 && kc==jr+1 && lr==0 &&lc==0&&kr==0){M[rid,cid]_psf}
if( jr>1 && kr>jr && kc==jr+1 && lr==0 && lc==kr+1)
{M[rid,cid]_psf}}
if(ic==lr && jc==1 && kc==jr+1 && lc==kr+1&& jr>1&&
kr>jr && lr>kr ){M[rid,cid]_psf}}
if(ir==0 && jr==0 && kr==0 && lr==0 && ic==1 && jc==0 && kc==0 && lc==0){M[rid,cid]_ps}
if(ir==0 && jr==0 && kr==0 && lr==0 && ic==1 && jc==1 && kc==0 && lc==0){M[rid,cid]_pf}
}}}}}}}}
for(i in 1:NN) { M[i,NN]_1-sum(M[i,]) }
Mn_M%*%M
for (i in 3:n) {Mn_Mn%*%M }
1-p0%*%Mn%*%U
}