UPCOJ 2679

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <stack>
#include <cstdlib>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#include <queue>

using namespace std;

const int N = 1e5+5;
const int MOD = 21092013;
char a[N],b[N],d[N];

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",a,b);
        int la=strlen(a),lb=strlen(b),ddd=0;
        for(int i=0; i<la; ++i)
        {
            if(a[i]==‘U‘)ddd = max(ddd-1,0);
            else d[ddd]=a[i],ddd++;
        }
        int ans=0,l=1,r=1;
        for(int i=0; i<lb; ++i)
        {
            if(b[i]==‘U‘)
            {
                ddd--;
                if(ddd<0)
                {
                    ddd=0;
                    continue;
                }
                ans++;
                ans%=MOD;
                if(d[ddd]==‘L‘) r++,r%=MOD;
                else l++,l%=MOD;
            }
            else if(b[i]==‘L‘)
            {
                ans=(ans+l)%MOD;
                r=(r+l)%MOD;
            }
            else
            {
                ans=(ans+r)%MOD;
                l=(l+r)%MOD;
            }
        }
        printf("Case %d: %d\n",++cas,ans+1);
    }
    return 0;
}