众所周知,异或是按位进行的。

那么不妨这道题也是按位处理。

显然,不能直接处理。

观察到$R$是由多个$S$拼成的,即它的状态可以由多个$S$首尾拼接而成。

考虑矩阵快速幂。

于是仅用处理$S$状态即可。

不妨假设选出来的数满足

$S>x_n>x_{n-1}>x_{n-2}>\ldots>x_1$

因为这样不重不漏。

最后统计答案时,即为这个的方案数。

状压$\text{DP}$状态$f_{i,j}$表示二进制从左往右前$i$位,

$j$从左往右第$k$位表示$x_k,x_{k+1}$的大小,若$x_{k+1}=x_{k}$,则为$1$,否则$x_{k+1}>x_k$为$0$。特别地,$x_{n+1}=S$

转移时枚举前$i-1$位的状态,然后根据这个选出合法的第$i$位状态,然后再进行转移。

特别地,初始状态$f_{0,s}$是为了进行矩阵快速幂而设计的。

矩阵快速幂记录一个头和尾的状态,这个部分可以参照代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
#define eps 1e-8
using namespace std;
const int N=(1<<7)+5,mod=1e9+7;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int dp[55][N],n,a[55],c[N];char s1[55];
I int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
I int get(int l,int r,int i)
{
    int v=0;
    for(int j=1;j<n;j++)if(l>>j&1)
    {
        int y=r>>j&1,z=r>>(j-1)&1;
        if(y>z)return -1;
        if(y==z)v|=1<<j;
    }
    if(l&1)
    {
        int y=r&1;
        if(y>a[i])return -1;
        if(y==a[i])v|=1;
    }
    return v;
}
int h[N][N],limit;
I void mul(int f[N][N],int g[N][N])
{
    for(int i=0;i<limit;i++)
        for(int j=0;j<limit;j++)
            h[i][j]=0;
    for(int i=0;i<limit;i++)
        for(int j=0;j<limit;j++)if(f[i][j])
            for(int k=0;k<limit;k++)
                h[i][k]=pls(h[i][k],(int)(1ll*f[i][j]*g[j][k]%mod));
    for(int i=0;i<limit;i++)
        for(int j=0;j<limit;j++)
            f[i][j]=h[i][j];
}
int f[N][N],g[N][N];
int main()
{
    qr(n);int k;qr(k);scanf("%s",s1+1);int m=strlen(s1+1);
    for(int i=1;i<=m;i++)a[i]=s1[i]^48;limit=1<<n;c[0]=1;
    for(int i=1;i<limit;i++)c[i]=c[i-(i&-i)]^1;
    for(int s=0;s<limit;s++)
    {
        for(int i=0;i<=m;i++)
            for(int j=0;j<limit;j++)
                dp[i][j]=0;
        dp[0][s]=1;
        for(int i=1;i<=m;i++)
            for(int l=0;l<limit;l++)if(dp[i-1][l])
                for(int r=0,j;r<limit;r++)if(c[r]&&(~(j=get(l,r,i))))
                    dp[i][j]=pls(dp[i][j],dp[i-1][l]);
        for(int i=0;i<limit;i++)
            f[i][s]=pls(f[i][s],dp[m][i]);
    }
    for(int i=0;i<limit;i++)g[i][i]=1; 
    for(;k;k>>=1,mul(f,f))if(k&1)mul(g,f);
    int ans=0;
    qw(g[0][limit-1]);puts("");
    return 0;
}