HDU6391

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=19260817;

int f[25][45];
int fac[45];
int facinv[45];
char s[45];
char t[45];

inline int add(int a,int b){
    return (a+=b)>=p?a-p:a;
}

inline int sub(int a,int b){
    return (a-=b)<0?a+p:a;
}

inline ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)(ans*=a)%=p;
        (a*=a)%=p;
        b>>=1;
    }
    return ans;
}

inline ll inv(ll a){
    return qpow(a,p-2);
}

inline ll C(int n,int m){
    return (n<m)?0:(ll)fac[n]*facinv[m]%p*facinv[n-m]%p;
}

signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int n,k;
    fac[0]=1;
    for(int i=1;i<=40;++i){
        fac[i]=(ll)fac[i-1]*i%p;
    }
    facinv[1]=1;
    for(int i=2;i<=40;++i){
        facinv[i]=(ll)(p-p/i)*facinv[p%i]%p;
    }
    facinv[0]=1;
    for(int i=1;i<=40;++i){
        facinv[i]=(ll)facinv[i]*facinv[i-1]%p;
    }
    for(int cas=1;;++cas){
        r(n),r(k);
        if(!n&&!k)return 0;
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=1;i<=k;++i){
            for(int j=0;j<=n;++j){
                if(j+3<=n)f[i][j+3]=add(f[i][j+3],f[i-1][j]*C(j,0)%p*C(n-j,3)%p);
                if(j+1<=n)f[i][j+1]=add(f[i][j+1],f[i-1][j]*C(j,1)%p*C(n-j,2)%p);
                if(j-1>=0)f[i][j-1]=add(f[i][j-1],f[i-1][j]*C(j,2)%p*C(n-j,1)%p);
                if(j-3>=0)f[i][j-3]=add(f[i][j-3],f[i-1][j]*C(j,3)%p*C(n-j,0)%p);
                if(i-2>=0)f[i][j]=sub(f[i][j],(ll)f[i-2][j]*(i-1)%p*sub(C(n,3),(i-2))%p);
            }
        }
        scanf("%s",s);
        scanf("%s",t);
        int cnt=0;
        for(int i=0;i<n;++i)if(s[i]!=t[i])cnt++;
        printf("Case #%d: %lld\n",cas,(ll)f[k][cnt]*facinv[k]%p*inv(C(n,cnt))%p);
    }
}