void work(int x,int prev)
{
    for (int i=head[x];i!=-1;i=edge[i].next)
    {
        if (edge[i].y==prev) continue;
        work(edge[i].y,x);
        for (int j=k;j>=0;j--)
        {
            f[x][j]+=f[edge[i].y][0]+edge[i].w*2;
            for (int l=0;l<j;l++)
            f[x][j]=min(f[x][j],f[x][l]+edge[i].w*(j-l)+f[edge[i].y][j-l]);
        }
    }
}

priority_queue <int, vector<int>, greater<int> > heap;
 
if (heap.size()<k) heap.push(temp);
else if (temp>heap.top())
    {
        heap.pop();
        heap.push(temp);
    }

typedef map<int, multiset<int> > dict;
 
void work(dict &a, dict &b, int &x)  //delete a(x) from b
{
    printf("%d\n",a[x].size());
    for (multiset<int>::iterator iter=a[x].begin();iter!=a[x].end();iter++)
    {
        b[*iter].erase(x);
    }
    a[x].clear();
}
 
int main()
{
    int n,m,x,y;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        if (n==0 && m==0) break;
        dict a,b;
        for (int i=0;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            a[x].insert(y);
            b[y].insert(x);
        }
        for (int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            if (x==0) work(a,b,y);
            else work(b,a,y);
        }
        printf("\n");
    }
    return 0;
}

void work(const int n)
{
    for (int k=0;k<n;k++)
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    {
        if (i==j || i==k || k==j) continue;
        if ((!visited[i][j]) && map[i][k]+map[k][j]==map[i][j])
        {
            ++c;
            visited[i][j]=true;
        }
    }
}

printf("%d\n",n*(n-1)-c);

map<string,int> num;

cin>>s1>>s2;
if (num.count(s1)) n1=num.find(s1)->second;
else
    {
        num.insert(make_pair(s1, ++count));
        n1=count;
        sn[n1]=s1;
    }
if (num.count(s2)) n2=num.find(s2)->second;
else
    {
        num.insert(make_pair(s2, ++count));
        n2=count;
        sn[n2]=s2;
    }
f[n1][++f[n1][0]]=n2;//f[n1]存n1的朋友们
f[n2][++f[n2][0]]=n1;

if (s[i]=='w' && s[i+1]=='b' && s[i+2]=='w') add(i,1);

int main()
{
    int t;
    int n,a,b;
    int i,j;
    double ans;
    double p[2010][4];
    double f[2010][4];
    double temp1,temp2,temp3;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d%d",&n,&a,&b);
        ans=0;
        for (i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&p[i][0],&p[i][1],&p[i][2],&p[i][3]);
        memset(f,0,sizeof(f));
        temp1=1;
        for (i=a;i<=b;i++)
        {
            if (i>n)
            {
                ans+=temp1;
                break;
            }
            for (j=1;j<=3;j++) f[i][j]=temp1*p[i][j];
            temp1*=p[i][0];
        }
        for (i=a;i<=n;i++)
        {
            temp1=temp2=temp3=1;
            for (j=i+a;j<=i+b;j++)
            {
                if (j>n)
                {
                    ans+=f[i][1]*temp1+f[i][2]*temp2+f[i][3]*temp3;
                    break;
                }
                else
                {
                    f[j][1]+=(f[i][2]*temp2+f[i][3]*temp3)*p[j][1]; //表示以这种状态踩在j
                    f[j][2]+=(f[i][1]*temp1+f[i][3]*temp3)*p[j][2];
                    f[j][3]+=(f[i][1]*temp1+f[i][2]*temp2+f[i][3]*temp3)*p[j][3];
                    temp1*=p[j][0]+p[j][1];  //tempi表示f[prev][i]不能走的概率
                    temp2*=p[j][0]+p[j][2];
                    temp3*=p[j][0];
                }
            }
            ans+=f[i][1]+f[i][2]+f[i][3];
        }
        printf("%.8lf\n",ans);
    }
    return 0;
}

for (i=1;i<=n;i++) f[1][i]=1;
for (int ii=0;ii<n;ii++)
{
    i=ii+2;
    if (str[ii]=='I')
    {
        f[i][1]=f[i-1][1];
        for (j=2;j<=n-i+1;j++) f[i][j]=(f[i-1][j]+f[i][j-1])%MOD;
    }
    else if (str[ii]=='D')
    {
        f[i][n-i+1]=f[i-1][n-i+2];
        for (j=n-i;j>=1;j--) f[i][j]=(f[i-1][j+1]+f[i][j+1])%MOD;
    }
    else
    {
        sum=0;
        for (j=1;j<=n-i+2;j++) sum=(sum+f[i-1][j])%MOD;
        for (j=1;j<=n-i+1;j++) f[i][j]=sum;
    }
}
printf("%d\n",f[n][1]);