思路

设牛 $i$的叫声串长度为 $l_i$。假设时刻 $X$时，牛 $i$所处在它的叫声串中的位置为 $a_i$，那么时刻 $X$一定满足若干形如 $X \equiv a_i \pmod{l_i}$的方程。

若所有 $l_i$是互质的，根据 CRT，$X$在 $[0,lcm(l_i))$中有唯一解，并且所有解可以表示为 $lcm(l_i)+X$的形式。将长度一样的叫声串合并为（若 $X$模 $l$余 $t$，叫声串长度为 $l$的牛有多少头会在叫）这种格式的信息后，依次考虑每种 $l$，DP 答案。

考虑一般的情况，两头牛 $i$和 $j$。设 $k=gcd(l_i,l_j)$。则 $X \bmod k = a_i \bmod k =a_j \bmod k$，所以只需要将叫声串中的元素按照模 $k$的余数分组，方程全改为 $\lfloor \frac{X}{k} \rfloor \equiv \lfloor \frac{a_i}{k} \rfloor \pmod{\frac{l_i}{k}}$。由于 $gcd(\frac{l_i}{k},\frac{l_j}{k})=1$，所以转化为了互质的情况（注意此时答案个数应该乘以 $\frac{50!}{k lcm(\frac{l_i}{k})}$而非 $\frac{50!}{lcm(\frac{l_i}{k})}）$。

但是现在牛有这么多头，两两之间 $k$不一样咋办？就加长叫声长度使得两两 $k$相等！

若 $l_i$只含有质因子 $2,3,5,7$，则 $2$因子不超过 $5$个，$3$因子不超过 $3$个，$5$和 $7$因子都不超过 $2$个，就将 $l_i$扩展到 $2 ^ 5 * 3 ^ 3 * 5 ^ 2 * 7 ^ 2$这么长。

若含有其他质因子 $p$，则只含有一个 $p$，并且最多还有 $2,3,5,7$中的 $2$和 $3$，并且有 $2$不超过 $2$个，有 $3$不超过 $1$个，所以扩展长度到 $2 * 2 * 3 * p$即可。

那么这些串的可能长度一共是 $12$种，两两长度的 gcd 都是 $12$，即可解决本题。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef pair<int,int> PR;
const int mod=10007,L1=1058400;
const int pri[4]={2,3,5,7},kpri[11]={11,13,17,19,23,29,31,37,41,43,47};
int n,kans[32],tmp[32],mo[12][1060000],cnt[32],vis[12];
vector<int> ans;vector<string> patterns;

int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void extension(int x,int y,int len) {
    vis[y]=1;int ll=patterns[x].length();int kjs=0;
    for(RI i=0;i<len;++i) if(patterns[x][i%ll]=='M') ++mo[y][i];
}
int getid(int x) {for(RI i=0;i<11;++i) if(kpri[i]==x) return i;}
class CowsMooing{
    public:
    vector<int> getDistribution(vector<string> kpat) {
        patterns=kpat,n=patterns.size();
        for(RI i=0;i<n;++i) {
            int kl=patterns[i].length();
            for(RI j=0;j<4;++j) while(kl%pri[j]==0) kl/=pri[j];
            if(kl==1) extension(i,11,L1);
            else extension(i,getid(kl),12*kl);
        }
        for(RI i=0;i<=n;++i) ans.push_back(0);
        int lcm=6107;//((50!)*12) mod 10007
        for(RI i=0;i<11;++i) if(vis[i]) lcm=1LL*lcm*ksm(kpri[i],mod-2)%mod;
        if(vis[11]) lcm=1LL*lcm*ksm(88200,mod-2)%mod;
        for(RI i=0;i<12;++i) {
            kans[0]=1;for(RI j=1;j<=n;++j) kans[j]=0;
            for(RI j=0;j<12;++j) {
                if(!vis[j]) continue;
                for(RI k=0;k<=n;++k) tmp[k]=kans[k],kans[k]=0;
                for(RI k=0;k<=n;++k) cnt[k]=0;
                for(RI k=i;k<(j==11?L1:12*kpri[j]);k+=12) ++cnt[mo[j][k]];
                for(RI k=0;k<=n;++k)
                    for(RI t=k;t<=n;++t)
                        kans[t]=qm(kans[t]+1LL*tmp[t-k]*cnt[k]%mod);
            }
            for(RI k=0;k<=n;++k) ans[k]=qm(ans[k]+kans[k]);
        }
        for(RI i=0;i<=n;++i) ans[i]=1LL*ans[i]*lcm%mod;
        return ans;
    }
};