## Editorial for Đồ chơi XYZ

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n,l,A[33],B[33],c[33],d[33],pre[33],f[33][33][33];
string a[6],b[6];

void calcPre(int A[],int c[])
{
int i=1,j=0;
while (i<=l)
{
while (j && A[i]!=A[j]) j=pre[j];
c[i]=j; j++; i++;
if (i>l || A[i]!=A[j]) pre[i]=j;
else pre[i]=pre[j];
}
}

int main()
{
cin >> n >> l;

for (int i=1;i<=5;i++) cin >> a[i];
for (int i=1;i<=l;i++)
for (int j=1;j<=5;j++)
A[i]+=(a[j][i-1]=='#')*(1<<(j-1));

for (int i=1;i<=5;i++) cin >> b[i];
for (int i=1;i<=l;i++)
for (int j=1;j<=5;j++)
B[i]+=(b[j][i-1]=='#')*(1<<(j-1));

calcPre(A,c);
calcPre(B,d);

f[0][0][0]=1;
for (int i=1;i<=n;i++)
for (int x=0;x<32;x++)
for (int j=0;j<=l;j++)
{
int jj=j;
if (j<l)
{
while (jj && A[jj+1]!=x) jj=c[jj];
if (A[jj+1]==x) jj++;
}
for (int k=0;k<=l;k++)
{
int kk=k;
if (k<l)
{
while (kk && B[kk+1]!=x) kk=d[kk];
if (B[kk+1]==x) kk++;
}
f[i][jj][kk]+=f[i-1][j][k];
f[i][jj][kk]%=1000000;
}
}
int re=0;
for (int j=0;j<l;j++) re=(re+f[n][j][l])%1000000;
for (int k=0;k<l;k++) re=(re+f[n][l][k])%1000000;
cout << re << endl;
}


#### Code mẫu của happyboy99x

#include<iostream>
#include<cstring>
#include<cassert>
#include<cstdio>
using namespace std;

const int N = 30, MOD = 1e6;
int pa[N], pb[N], na[N], nb[N], n, len;

void getPattern(int a[]) {
string s[5];
for(int i = 0; i < 5; ++i) cin >> s[i];
for(int i = 0; i < len; ++i) {
a[i] = 0;
for(int j = 0; j < 5; ++j)
if(s[j][i] == '#') a[i] |= 1 << j;
}
}

void enter() {
cin >> n >> len;
getPattern(pa);
getPattern(pb);
}

void buildFailure(int a[], int next[]) {
next[0] = -1;
for(int i = 1, j = -1; i < len; ++i) {
while(j >= 0 && a[i] != a[j + 1]) j = next[j];
if(a[i] == a[j + 1]) ++j;
next[i] = j;
}
}

int f[N + 1][N + 1][N + 1][2];

int dp(int a[], int b[], int na[], int nb[]) {
memset(f, 0, sizeof f);
f[0][0][0][0] = 1;
int res = 0;
for(int i = 0; i <= n; ++i)
for(int ma = 0; ma <= len; ++ma)
for(int mb = 0; mb < len; ++mb)
for(int c = 0; c < 2; ++c) if(f[i][ma][mb][c] > 0) {
if(i == n) {
if(c == 1) (res += f[i][ma][mb][c]) %= MOD;
} else {
int tma = ma - 1, tmb = mb - 1;
if(tma == len - 1) tma = na[tma];
while(tma >= 0 && a[tma + 1] != mask) tma = na[tma];
if(a[tma + 1] == mask) ++tma;
while(tmb >= 0 && b[tmb + 1] != mask) tmb = nb[tmb];
if(b[tmb + 1] == mask) ++tmb;
(f[i + 1][tma + 1][tmb + 1][c | (tma == len - 1 ? 1 : 0)] += f[i][ma][mb][c]) %= MOD;
}
}
}
return res;
}

int main() {
#ifdef __DNK__
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(false);
enter();
buildFailure(pa, na);
buildFailure(pb, nb);
cout << (dp(pa, pb, na, nb) + dp(pb, pa, nb, na)) % MOD;
return 0;
}


#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

const int N = 33;
const int MOD = 1000000;

using namespace std;

int n, L;

int ret = 0;
FOR(i, 0, 5)
if (a[i] == '#')
ret |= 1 << i;
return ret;
}

FOR(i, 0, 5)
if (mask & (1 << i))
a[i] = '#';
else
a[i] = '.';
}

void makeLove(char a[][5], int fail[][N]) {
int kmp[N];
kmp[0] = 0;
FOR(i, 1, L)  {
int j = kmp[i - 1];
while (j && !equal(a[i], a[i] + 5, a[j])) j = kmp[j - 1];
kmp[i] = j + equal(a[i], a[i] + 5, a[j]);
//if (kmp[i]) cerr << i << ' ' << kmp[i] << endl;
}
RESET(fail, 0);
FOR(matched, 1, L) FOR(mask, 0, 32) {
char tmp[5];
int j = matched;
while (j && !equal(a[j], a[j] + 5, tmp)) j = kmp[j - 1];
fail[matched][mask] = j + (equal(a[j], a[j] + 5, tmp));
/*
cerr << "fail " << matched << ' ' << mask << ' ' << fail[matched][mask] << endl;
}
*/
}
}

void add(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}

int f[N][N][N]; //* pos, matchedA, matchedB
int fail[2][N][N];
char a[2][N][5];

int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen("XYZ.inp", "r", stdin);
cin >> n >> L;
FOR(t, 0, 2) {
FOR(i, 0, 5) FOR(j, 0, L)
cin >> a[t][j][i];
/*
FOR(i, 0, L) {
FOR(j, 0, 5) cout << a[t][i][j];
cout << endl;
}
cout << endl;
*/
makeLove(a[t], fail[t]);
}
f[0][0][0] = 1;
FOR(i, 0, n) FOR(more, 0, 32) {
REP(matchA, 0, L) REP(matchB, 0, L)
if (f[i][matchA][matchB])
}
int ans = 0;
FOR(i, 0, L) {
}
cout << ans << endl;
return 0;
}


#### Code mẫu của RR

{$R+,Q+} {$Mode objFPC}
uses math;
const
FINP='';
FOUT='';
MAXN=31;
oo=1000000;
var
f1,f2:text;
l,n:longint;
d1,d2:array[0..MAXN,0..MAXN,0..MAXN,0..1] of longint;
a,b:array[1..5,1..30] of longint;
p1,p2:array[0..30] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i,j:longint;
ch:char;
begin
for i:=1 to 5 do
begin
for j:=1 to l do
begin
if ch='.' then a[i,j]:=0 else a[i,j]:=1;
end;
end;
for i:=1 to 5 do
begin
for j:=1 to l do
begin
if ch='.' then b[i,j]:=0 else b[i,j]:=1;
end;
end;
end;
function check1(ll,v1,v2,v3,v4,v5:longint):boolean;
begin
check1:=false;
if ll>l then exit;
if ll<=0 then exit(true);
if v1<>a[1,ll] then exit;
if v2<>a[2,ll] then exit;
if v3<>a[3,ll] then exit;
if v4<>a[4,ll] then exit;
if v5<>a[5,ll] then exit;
check1:=true;
end;
function check2(ll,v1,v2,v3,v4,v5:longint):boolean;
begin
check2:=false;
if ll>l then exit;
if ll<=0 then exit(true);
if v1<>b[1,ll] then exit;
if v2<>b[2,ll] then exit;
if v3<>b[3,ll] then exit;
if v4<>b[4,ll] then exit;
if v5<>b[5,ll] then exit;
check2:=true;
end;
procedure solve;
var
i,l1,l2,k,ll1,ll2,kk:longint;
v1,v2,v3,v4,v5:longint;
begin
d1[0,0,0,0]:=1; d2[0,0,0,0]:=1;
for i:=0 to n-1 do
for l1:=0 to l do
for l2:=0 to l-1 do
for k:=0 to 1 do
if d1[i,l1,l2,k]>0 then
for v1:=0 to 1 do
for v2:=0 to 1 do
for v3:=0 to 1 do
for v4:=0 to 1 do
for v5:=0 to 1 do
begin
if (i=1) and (l1=1) and (l2=0) and (k=0)
and (v1+v3+v4+v5=0) and (v2=1) then
write('');
if check1(l1+1,v1,v2,v3,v4,v5) then ll1:=l1+1
else
begin
ll1:=l1;
while not check1(ll1+1,v1,v2,v3,v4,v5) do
ll1:=p1[ll1];
inc(ll1);
end;
if check2(l2+1,v1,v2,v3,v4,v5) then ll2:=l2+1
else
begin
ll2:=l2;
while not check2(ll2+1,v1,v2,v3,v4,v5) do
ll2:=p2[ll2];
inc(ll2);
end;
if ll1=l then kk:=1 else kk:=k;
if ll2<l then
begin
d1[i+1,ll1,ll2,kk]+=d1[i,l1,l2,k];
if d1[i+1,ll1,ll2,kk]>oo then d1[i+1,ll1,ll2,kk]-=oo;
end;
end;
for i:=0 to n-1 do
for l1:=0 to l-1 do
for l2:=0 to l do
for k:=0 to 1 do
if d2[i,l1,l2,k]>0 then
for v1:=0 to 1 do
for v2:=0 to 1 do
for v3:=0 to 1 do
for v4:=0 to 1 do
for v5:=0 to 1 do
begin
if check1(l1+1,v1,v2,v3,v4,v5) then ll1:=l1+1
else
begin
ll1:=l1;
while not check1(ll1+1,v1,v2,v3,v4,v5) do
ll1:=p1[ll1];
inc(ll1);
end;
if check2(l2+1,v1,v2,v3,v4,v5) then ll2:=l2+1
else
begin
ll2:=l2;
while not check2(ll2+1,v1,v2,v3,v4,v5) do
ll2:=p2[ll2];
inc(ll2);
end;
if ll2=l then kk:=1 else kk:=k;
if ll1<l then
begin
d2[i+1,ll1,ll2,kk]+=d2[i,l1,l2,k];
if d2[i+1,ll1,ll2,kk]>oo then d2[i+1,ll1,ll2,kk]-=oo;
end;
end;
end;
procedure ans;
var
l1,l2,k,sum:longint;
begin
sum:=0;
for l1:=0 to l do
for l2:=0 to l do
for k:=1 to 1 do
begin
sum+=d1[n,l1,l2,k]; if sum>oo then sum-=oo;
sum+=d2[n,l1,l2,k]; if sum>oo then sum-=oo;
end;
writeln(f2,sum mod oo);
end;
function kt1(l1,r1,l2,r2:longint):boolean;
var
i1,i2,h:longint;
begin
kt1:=false;
for i1:=l1 to r1 do
for i2:=l2 to r2 do
for h:=1 to 5 do
if a[h,i1]<>a[h,i2] then exit;
kt1:=true;
end;
function kt2(l1,r1,l2,r2:longint):boolean;
var
i1,i2,h:longint;
begin
kt2:=false;
for i1:=l1 to r1 do
for i2:=l2 to r2 do
for h:=1 to 5 do
if b[h,i1]<>b[h,i2] then exit;
kt2:=true;
end;
procedure init;
var
i,j:longint;
begin
p1[1]:=0; p1[0]:=-1;
for i:=2 to l do
for j:=i-1 downto 1 do
if kt1(1,j,i-j+1,i) then
begin
p1[i]:=j;
break;
end;
p2[1]:=0; p2[0]:=-1;
for i:=2 to l do
for j:=i-1 downto 1 do
if kt2(1,j,i-j+1,i) then
begin
p2[i]:=j;
break;
end;
end;
begin
openF;
inp;
init;
solve;
ans;
closeF;
end.


#### Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   44
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
const int mod=(int)1e6;
const int m=5;
int s[MAX],t[MAX];
int n,len;
int f[MAX][MAX][MAX][2][2];
int kmpS[MAX],kmpT[MAX];
int nextS[MAX][MAX],nextT[MAX][MAX];
void add(int &x,const int &y) {
x+=y;
if (x>=mod) x-=mod;
}
void init(void) {
char inp[MAX][MAX];
scanf("%d%d",&n,&len);
REP(i,m) scanf("%s",inp[i]+1);
FOR(i,1,len) {
}
REP(i,m) scanf("%s",inp[i]+1);
FOR(i,1,len) {
}
}
void KMP(int s[],int kmp[],int next[][MAX]) {
int j=kmp[1]=0;
FOR(i,2,len) {
while (j>0 && s[j+1]!=s[i]) j=kmp[j];
if (s[j+1]==s[i]) j++;
kmp[i]=j;
}
int j=i;
while (j>0 && (j>=len || s[j+1]!=k)) j=kmp[j];
if (j<len && s[j+1]==k) j++;
next[i][k]=j;
}
}
void process(void) {
KMP(s,kmpS,nextS);
KMP(t,kmpT,nextT);
f[0][0][0][0][0]=1;
REP(i,n) REP(preS,len+1) REP(preT,len+1) REP(s,2) REP(t,2) if (f[i][preS][preT][s][t]>0)
int ls=nextS[preS][chs];
int lt=nextT[preT][chs];
}
int res=0;
REP(i,len+1) REP(j,len+1) {
}
printf("%d\n",res);
}
int main(void) {
init();
process();
return 0;
}


#### Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int N, L;
int F[33][33][33];
int a[33], b[33];
int na[33][33], nb[33][33];

void init(int na[33][33], int a[33]) {
for(int len=0;len<L;++len)
for(int r=0;r<=len+1;++r) {
bool ok = true;
for(int j=0;j<r;++j) if((j+1==r && a[j]!=ad) || (j+1<r && a[j]!=a[len-r+1+j])) ok = false;
}
}

int main() {
char c;
cin >> N >> L;
for(int i=0;i<5;++i)
for(int j=0;j<L;++j)
if(cin >> c, c=='#') a[j] = a[j] * 2 + 1;
else a[j] = a[j] * 2;
for(int i=0;i<5;++i)
for(int j=0;j<L;++j)
if(cin >> c, c=='#') b[j] = b[j] * 2 + 1;
else b[j] = b[j] * 2;
init( na, a);
init( nb, b);
F[0][0][0] = 1;
for(int i=0;i<N;++i)
for(int j=0;j<=L;++j)
for(int k=0;k<=L;++k)
int res = 0;
for(int i=0;i<=L;++i)
for(int j=0;j<=L;++j)
if((i==L) ^ (j==L)) res = (res + F[N][i][j]) % 1000000;
printf("%d\n", res);
return 0;
}