Progressive hard octave rock tunes (so-called “phorts”) are written using a specifific music notation. This flflavor of rock is built on just 13 difffferent note pitches, other pitches (in other octaves)are considered to be an outdated musical ballast. Each note can be either a long one or a shortone. Consequently, there are exactly 26 difffferent notes in the rock.

You are going to compose a phort tune on the occasion of your friend’s birthday and perform itwith your band on the main town square. While composing the phort, you need to avoid certainmusical phrases, which are heavily copyrighted as a result of long research sponsored by bigrecord companies. It has been established that these phrases are very catchy, easy to remember,and could be exploited to bind the listeners subconsciously to a particular music company whichwould utilize these phrases in their production.

The tune is a sequence of notes. A musical phrase is also a sequence of notes and it is consideredto be contained in a tune if its notes form a contiguous subsequence of the tune, which meansthe same notes appear in the tune right after each other in the same order.

Fortunately, only a few forbidden phrases have been patented so far. Thus, you have a relativefreedom in composing your own tunes. In particular, you are interested in the number ofacceptable tunes of some length. An acceptable tune is any tune which does not contain aforbidden phrase. The length of the tune is equal to the number of notes it contains.

#### 链接 🔗

「ICPC Central Europe Regional Contest 2019」 G. K==S

#### 代码

const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = acos(-1);
const int N = 2e5+10;
struct AC_Automaton
{
ll ch[N][26],fail[N],cnt[N],tot;
void init()
{
MM(ch,-1);MM(fail,0);MM(cnt,0);
tot = 0;
}
void insert(char *s)
{
ll p = 0,len = strlen(s);
FOR(i,0,len-1)
{
if(ch[p][s[i] - 'a'] == -1) ch[p][s[i]-'a'] = ++tot;
p = ch[p][s[i] - 'a'];
}
cnt[p]++;
}
void build()
{
queue<ll> que;
FOR(i,0,25)
{
if(ch[0][i] == -1) ch[0][i] = 0;
else que.push(ch[0][i]);
}
while(!que.empty())
{
ll p = que.front(); que.pop();
FOR(i,0,25)
{
if(ch[p][i] == -1) ch[p][i] = ch[fail[p]][i];
else
{
fail[ch[p][i]] = ch[fail[p]][i], que.push(ch[p][i]);
cnt[ch[p][i]] |= cnt[ch[fail[p]][i]];
}
}
}
}
}AC;
char s[201];
struct Matrix_Pow
{
ll n;
struct matrix
{
long long a[205][205];
}ans,base,C;
void init()
{
MM(ans.a,0);
MM(base.a,0);
FOR(i,1,204) ans.a[i][i] = 1;
}
matrix matrix_mul(matrix A, matrix B)
{
matrix C;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
C.a[i][j] = 0;
for (int k = 1; k <= n; ++k) C.a[i][j] = (C.a[i][j] + (A.a[i][k] * B.a[k][j] % mod)) % mod;
}
return C;
}
void matrix_pow(long long b)
{
for (; b; b >>= 1)
{
if (b & 1) ans = matrix_mul(ans, base);
base = matrix_mul(base, base);
}
}
}M;
int main()
{
//    __IN;__OUT;
ll n,m;RLL2(n,m);
AC.init();
FOR(i,1,m)
{
ll x;RLL(x);
RS(s);
AC.insert(s);
}
AC.build();
M.init();
M.n = AC.tot+1;
FOR(i,0,AC.tot)
{
if(AC.cnt[i]) continue;
FOR(j,0,25)
{
ll v = AC.ch[i][j];
if(AC.cnt[v]) continue;
if(AC.ch[i][j] == -1) v = 0;
M.base.a[i+1][v+1]++;
}
}
M.matrix_pow(n);
ll ans = 0;
FOR(i,1,AC.tot+1)
ans = (ans + M.ans.a[1][i])%mod;
PLN(ans);
return 0;
}