// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define VI vector<int>
#define VII vector<vector<int>>
#define VIII vector<vector<vector<int>>>
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x), __VA_ARGS__})
#define cmax(x,...) x=max({(x), __VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010
#define P 1000000007
struct trie {
int base, N;
struct node {
int isword, c;
vector<node*> ch;
node *parent = nullptr;
};
node *root;
vector<node> datalist;
int total = 0;
node *newnode(int c, node *p = nullptr) {
node *x = &datalist[total++];
x->ch.resize(N, 0);
x->c = c;
x->parent = p;
return x;
}
trie(int M, char L = 0, char R = 127) {
base = L;
N = R - L + 1;
datalist.resize(M);
root = newnode(-1);
}
void insert(string s) {
node *x = root;
for (char c: s) {
if (!x->ch[c - base]) {
x->ch[c - base] = newnode(c - base, x);
}
x = x->ch[c - base];
}
x->isword = 1;
}
string get(node *x) {
vector<char> v;
while (x->parent) {
v.push_back(x->c + base);
x = x->parent;
}
reverse(v.begin(), v.end());
string res(v.begin(), v.end());
return res;
}
void graphviz_dump(string filename = "graph.dot") {
FILE *f = fopen(filename.c_str(), "w");
fprintf(f, "digraph {\n");
rep(i, 0, total) {
node *x = &datalist[i];
fprintf(f, " %lld;\n", i, (x->c >= 0 ? char(x->c + base) : ' '), x->isword ? "red" : "black");
}
queue<node*> q; q.push(root);
while (!q.empty()) {
node *x = q.front(); q.pop();
rep(i, 0, N) {
if (x->ch[i]) {
fprintf(f, " %ld -> %ld;\n", x - &datalist[0], x->ch[i] - &datalist[0]);
q.push(x->ch[i]);
}
}
}
fprintf(f, "}\n");
}
void solve(string s) {
vector<int> dp(sz(s)+1, 0);
dp[0] = 1;
rep(i, 0, sz(s)+1) {
if (!dp[i]) continue;
node *x = root;
int j = i;
while (j < sz(s) && x->ch[s[j] - base]) {
x = x->ch[s[j] - base];
if (x->isword) dp[j+1] += dp[i], dp[j+1] %= P;
++j;
}
}
cout << dp[sz(s)] << endl;
}
};
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
string s; cin >> s;
int n; cin >> n;
trie t(1e6+1, 'a', 'z');
rep(i, 0, n) {
string x; cin >> x;
t.insert(x);
}
// t.graphviz_dump();
t.solve(s);
return 0;
}
No Comments