## Editorial for Tách từ

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

const fi='';
z=1337377;
type pointer=^node;
node=record
cnt:longint;
next:array['a'..'z'] of pointer;
end;
var n,i,j:longint;
a,s:ansistring;
top:pointer;
f:array[0..300030] of longint;

function create:pointer;
var c:char; p:pointer;
begin
new(p); p^.cnt:=0;
for c:='a' to 'z' do p^.next[c]:=nil;
exit(p);
end;

procedure put(p:pointer;pos:longint;s:ansistring);
var t:pointer;
begin
if p^.next[s[pos]]=nil then p^.next[s[pos]]:=create;
t:=p^.next[s[pos]];
if pos<length(s) then put(t,pos+1,s)
else inc(t^.cnt);
end;

procedure check(p:pointer;pos,x:longint);
var t:pointer;
begin
if p^.next[a[pos+x]]=nil then exit;
t:=p^.next[a[pos+x]];
if t^.cnt>0 then
begin
f[pos+x]:=f[pos+x]+f[x];
if f[pos+x]>=z then f[pos+x]:=f[pos+x]-z;
end;
if (pos<100) and (pos+x<n) then check(t,pos+1,x);
end;

begin
assign(input,fi); reset(input);
top:=create;
for i:=1 to n do
begin
put(top,1,s);
end;
n:=length(a);
f[0]:=1;
for i:=0 to n-1 do check(top,1,i);
writeln(f[n]);
close(input);
end.


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

#include<cstdio>
#include<cstring>

const int N = 4000 + 2, L = 300000 + 2, WL = 100 + 2, MOD = 1337377;
struct TrieNode {
int next[26], nfinish;
} trie[N * WL];
int nnode = 1, n, f[L];
char tmp[WL], s[L];

void insert(const char * s) {
int u = 0;
for(int i = strlen(s) - 1; i >= 0; --i) {
int t = s[i] - 0x61;
if(trie[u].next[t] == 0) trie[u].next[t] = nnode++;
u = trie[u].next[t];
}
trie[u].nfinish = 1;
}

void enter() {
scanf("%s%d", s+1, &n);
for(int i = 0; i < n; ++i) {
scanf("%s", tmp);
insert(tmp);
}
}

void solve() {
f[0] = 1; int l = strlen(s + 1);
for(int i = 1; i <= l; ++i) {
int u = 0;
for(int j = i; j && trie[u].next[s[j] - 0x61]; --j)
if(trie[u = trie[u].next[s[j] - 0x61]].nfinish)
f[i] = (f[j-1] + f[i]) % MOD;
}
printf("%d\n", f[l]);
}

int main() {
enter();
solve();
return 0;
}


#include <bits/stdc++.h>
const int N = 300005;
const int MOD = 1337377;
using namespace std;
char s[N], aa[111];
int f[N];
int n;

struct node {
int a[26]; int e;
int& operator[] (int i) {return a[i];}
node() {for(int i=0; i<26; i++) a[i] = 0; e = 0;}
};

vector<node> a;

int pos = 0, i, c;
for(i=0; c = s[i]; i++) {
if (a[pos][c - 'a'] == 0) {
a.push_back(node());
a[pos][c - 'a'] = a.size() - 1;
}
pos = a[pos][c - 'a'];
}
a[pos].e = 1;
}

int main()
{
gets(s); scanf("%d\n", &n);
int i, j, pos, c;
a.push_back(node());
for(i=1;i<=n; i++) {
}
f[0] = 1;
for(i=0; s[i]; i++) {
pos = 0;
for(j=i; c = s[j]; j++) {
if (a[pos][c - 'a'] == 0) break;
pos = a[pos][c - 'a'];
if (a[pos].e == 1) f[j+1] = (f[j+1] + f[i]) % MOD;
}
}
printf("%d\n", f[strlen(s)]);
return 0;
}


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

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{\$R-,Q-}
const
FINP='';
FOUT='';
MAXN=300111;
oo=1337377;
type
trie=^node;
node=record
c:integer;
d:array['a'..'z'] of trie;
end;
var
s:ansistring;
n:longint;
root:trie;
d:array[0..MAXN] of longint;
var
ch:char;
begin
new(t); t^.c:=0;
for ch:='a' to 'z' do t^.d[ch]:=nil;
end;
procedure inp;
var
a:string;
i,j,m,l:longint;
x:trie;
begin
assign(input,FINP); reset(input);
for i:=1 to m do
begin
x:=root;
for j:=l downto 1 do
begin
x:=x^.d[a[j]];
end;
inc(x^.c);
end;
close(input);
end;
procedure solve;
var
i,j:longint;
x:trie;
begin
d[0]:=1;
for i:=1 to n do
begin
x:=root; j:=i;
while (j>0) and (x^.d[s[j]]<>nil) do
begin
x:=x^.d[s[j]];
dec(j);
if x^.c=1 then inc(d[i],d[j]);
end;
d[i]:=d[i] mod oo;
end;
writeln(d[n]);
end;
begin
inp;
solve;
end.


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

#include <cmath>
#include <cstring>
#include <iostream>
#define MOD 1337377
using namespace std;

struct trie
{
int val;
int d[26];
} tx[400110];

int n,k,cnt = -1;
char S[300010];
char a[105];
int F[300010];

int create()
{
cnt++;  tx[cnt].val = 0;
memset(tx[cnt].d,-1,sizeof(tx[cnt].d));
return cnt;
}

int main()
{
//  freopen("strings.inp","r",stdin);
//  freopen("strings.out","w",stdout);
scanf("%s", &S);  n = strlen(S);
int tmp = create();

scanf("%d", &k);
for (int i = 0; i < k; i++)
{
scanf("%s", &a);
int s = 0;
for (int j = 0; j < strlen(a); j++)
{
int next = tx[s].d[a[j] - 'a'];
if (next < 0)
{
next = create();
tx[s].d[a[j] - 'a'] = next;
}
s = next;
}
tx[s].val++;
}

memset(F,0,sizeof(F));
F[n] = 1;
for (int i = n - 1; i >= 0; i--)
{
int s = 0,j = i;
while (j < n)
{
s = tx[s].d[S[j] - 'a'];
if (s < 0) break;
j++;
F[i] = (F[i] + tx[s].val * F[j]) % MOD;
}
}
printf("%d\n", F[0]);
}


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

#include <iostream>
#include <cstdio>

using namespace std;

struct Trie {
bool last;
Trie * n[26];
};

Trie container[800000];
int ncon;

int n, N;
char a[300030], tmp[444];
Trie root;
int f[300030];
const int mod = 1337377;

void add( char * a) {
Trie * p = &root;
for(int i=0;a[i]!=0;++i) {
int t = a[i] - 'a';
if(p->n[t]!=NULL) p = p->n[t];
else {
p->n[t] = container + ++ncon;
p = p->n[t];
}
}
p->last = true;
}

int main() {
gets(a);
n = strlen(a);
scanf("%d", &N);
gets(tmp);
for(int i=0;i<N;++i) {
gets(tmp);
}
f[n] = 1;
for(int i=n-1;i>=0;--i) {
Trie * p = &root;
for(int j=i;j<n;++j) {
int t = a[j] - 'a';
if(p->n[t]==NULL) break;
p = p->n[t];
if(p->last) f[i] += f[j+1];
}
f[i] %= mod;
}
cout << f[0] << endl;
//system("pause");
return 0;
}