Luogu

分析

先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。

考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_i>A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直接枚举所有数下一位填什么即可。

注意到 $R$ 串的循环节为 $k$，因此我们可以预处理出每个状态在一个 $S$ 串后变成另一个状态的方案数，然后矩阵快速幂即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X;
}

const int mod=1e9+7;

int n,k,l; char s[60];
int dp[60][1<<7];

struct Matrix {
    int s[1<<7][1<<7];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} Q;
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (re int i=0;i<1<<n;++i)
        for (re int j=0;j<1<<n;++j)
            for (re int k=0;k<1<<n;++k)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod;
    return c;
}
inline Matrix qpow(Matrix a,int b) {
    Matrix c; for (re int i=0;i<1<<n;++i) c[i][i]=1;
    while (b) {
        if (b&1) c=c*a;
        b>>=1,a=a*a;
    }
    return c;
}

inline int trans(int S,int t,int w) {
    int T=0;
    if (S&1) {
        for (re int i=0;i<n&&(S&(1<<i));++i)
            if (!w&&(t&(1<<i))) return -1;
        if ((t&1)==w) T|=1;
    }
    for (re int i=1;i<n;++i) {
        if (!(S&(1<<i))) continue;
        int x=(t>>i)&1,y=(t>>(i-1))&1;
        if (x>y) return -1;
        if (x==y) T|=1<<i;
    }
    return T;
}

int main() {
    n=read(),k=read(); scanf("%s",s+1); l=strlen(s+1);
    for (re int sta=0;sta<1<<n;++sta) {
        memset(dp,0,sizeof(dp)); dp[0][sta]=1;
        for (re int i=0;i<l;++i)
            for (re int S=0;S<1<<n;++S) {
                if (!dp[i][S]) continue;
                for (re int t=0;t<1<<n;++t) {
                    if (__builtin_parity(t)) continue;
                    int T=trans(S,t,s[i+1]-'0');
                    if (~T) dp[i+1][T]=(dp[i+1][T]+dp[i][S])%mod;
                }
            }
        for (re int S=0;S<1<<n;++S) Q[sta][S]=dp[l][S];
    }
    printf("%d\n",qpow(Q,k)[(1<<n)-1][0]);
    return 0;
}