lightoj 1299

/* keu kono jayga chere dile akta faka jayga + akta na bosha manush hate thake...mane faka jayga + manush er sonkha always soman vabe bare othoba kome....jokon U pabo tokon dekbo ager na bosa manush gula aei jayga e bosbe othoba bosbe na...ar jokon D pabo tokon ager faka jayga er manush gula aei jayga er sathe swap korbe othoba korbe na...*/


ll dp[1002][1002];char s[1005];int vis[1002][1002],ajinka,len;

ll giveres(int pos,int baki)
{
    if(baki<0)return 0;
    if(pos==len)return (baki==0);
    int &ret = vis[pos][baki];
    if(ret==ajinka)return dp[pos][baki];
    dp[pos][baki] = 0;
    ret = ajinka;
    if(s[pos]=='E')dp[pos][baki] = giveres(pos+1,baki);
    else if(s[pos]=='U')
    {
        dp[pos][baki] = baki * giveres(pos+1,baki);
        dp[pos][baki]%=mod;
        dp[pos][baki]+=giveres(pos+1,baki+1);
        dp[pos][baki]%=mod;
    }
    else {
        dp[pos][baki] = baki * giveres(pos+1,baki);
        dp[pos][baki]%=mod;
        dp[pos][baki]+=baki * baki * giveres(pos+1,baki-1);
        dp[pos][baki]%=mod;

    }
    return dp[pos][baki];
}


int main()
{
    //booster()
    ///read("input.txt");
    int t;
    scani(t);
    ajinka = 1;
    while(t--){

        scanf(" %s",s);
        len = strlen(s);
        printf("Case %d: %lld\n",ajinka++,giveres(0,0));
    }


    return 0;
}