const int MAXN = 404, MOD = 1e9 + 7, sigma = 26;
int term[MAXN], len[MAXN], to[MAXN][sigma], link[MAXN], sz = 1;
void add_str(string s)
{
int cur = 0;
for(auto c: s)
{
if(!to[cur][c - 'a'])
{
to[cur][c - 'a'] = sz++;
len[to[cur][c - 'a']] = len[cur] + 1;
}
cur = to[cur][c - 'a'];
}
term[cur] = cur;
}
void push_links()
{
int que[sz];
int st = 0, fi = 1;
que[0] = 0;
while(st < fi)
{
int V = que[st++];
int U = link[V];
if(!term[V]) term[V] = term[U];
for(int c = 0; c < sigma; c++)
if(to[V][c])
{
link[to[V][c]] = V ? to[U][c] : 0;
que[fi++] = to[V][c];
}
else
{
to[V][c] = to[U][c];
}
}
}
Y29uc3QgaW50IE1BWE4gPSA0MDQsIE1PRCA9IDFlOSArIDcsIHNpZ21hID0gMjY7CgppbnQgdGVybVtNQVhOXSwgbGVuW01BWE5dLCB0b1tNQVhOXVtzaWdtYV0sIGxpbmtbTUFYTl0sIHN6ID0gMTsKdm9pZCBhZGRfc3RyKHN0cmluZyBzKQp7CiAgICBpbnQgY3VyID0gMDsKICAgIGZvcihhdXRvIGM6IHMpCiAgICB7CiAgICAgICAgaWYoIXRvW2N1cl1bYyAtICdhJ10pCiAgICAgICAgewogICAgICAgICAgICB0b1tjdXJdW2MgLSAnYSddID0gc3orKzsKICAgICAgICAgICAgbGVuW3RvW2N1cl1bYyAtICdhJ11dID0gbGVuW2N1cl0gKyAxOwogICAgICAgIH0KICAgICAgICBjdXIgPSB0b1tjdXJdW2MgLSAnYSddOwogICAgfQogICAgdGVybVtjdXJdID0gY3VyOyAKfQoKdm9pZCBwdXNoX2xpbmtzKCkKewogICAgaW50IHF1ZVtzel07CiAgICBpbnQgc3QgPSAwLCBmaSA9IDE7CiAgICBxdWVbMF0gPSAwOwogICAgd2hpbGUoc3QgPCBmaSkKICAgIHsKICAgICAgICBpbnQgViA9IHF1ZVtzdCsrXTsKICAgICAgICBpbnQgVSA9IGxpbmtbVl07CiAgICAgICAgaWYoIXRlcm1bVl0pIHRlcm1bVl0gPSB0ZXJtW1VdOwogICAgICAgIGZvcihpbnQgYyA9IDA7IGMgPCBzaWdtYTsgYysrKQogICAgICAgICAgICBpZih0b1tWXVtjXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGlua1t0b1tWXVtjXV0gPSBWID8gdG9bVV1bY10gOiAwOwogICAgICAgICAgICAgICAgcXVlW2ZpKytdID0gdG9bVl1bY107CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0b1tWXVtjXSA9IHRvW1VdW2NdOwogICAgICAgICAgICB9CiAgICB9Cn0=