#include using namespace std; const int MOD = 1000000007; const int WORD = 5005; int add(int a, int b) { return (1LL * a + b) % MOD; } int sub(int a, int b) { a %= MOD; b %= MOD; return (a + MOD - b) % MOD; } int mul(int a, int b) { return (1LL * a * b) % MOD; } string txt; int nWord; string word[WORD]; void read() { cin >> txt; cin >> nWord; for (int i = 0; i < nWord; ++i) { cin >> word[i]; } } int calc(string &wd) { if (txt.size() < wd.size()) return 0; int targetHash = 0; for (int i = 0; i < wd.size(); ++i) { targetHash = add(mul(targetHash, 256), wd[i]); } int currHash = 0; for (int i = 0; i < wd.size(); ++i) { currHash = add(mul(currHash, 256), txt[i]); } int p = 1; for (int i = 0; i < wd.size() - 1; ++i) { p = mul(p, 256); } int cnt = 0; for (int i = 0; i + wd.size() <= txt.size(); ++i) { if (currHash == targetHash) { ++cnt; } currHash = sub(currHash, mul(p, txt[i])); currHash = mul(currHash, 256); currHash = add(currHash, txt[i + wd.size()]); } return cnt; } void work() { int sum = 0; for (int i = 0; i < nWord; ++i) { sum += calc(word[i]); } cout << sum << endl; } int main() { read(); work(); return 0; }