Shared code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "C:/Users/sudhi/OneDrive/Desktop/CP/ac-library/atcoder/debug.hpp"
#else
#define debug(...) 69
#endif

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

#pragma once

// Arithmetic mod 2^64-1. 2x slower than mod 2^64 and more
// code, but works on evil test data (e.g. Thue-Morse, where
// ABBA... and BAAB... of length 2^10 hash the same mod 2^64).
// "typedef ull H;" instead if you think test data is random,
// or work mod 10^9+7 if the Birthday paradox is not a problem.
typedef uint64_t ull;
struct H {
    // H is a type that uses arithmetic modulo 2^64 - 1 to compute hashes
	ull x; H(ull x=0) : x(x) {}
	H operator+(H o) { return x + o.x + (x + o.x < x); }
	H operator-(H o) { return *this + ~o.x; }
	H operator*(H o) { auto m = (__uint128_t)x * o.x;
		return H((ull)m) + (ull)(m >> 64); }
	ull get() const { return x + !~x; }
	bool operator==(H o) const { return get() == o.get(); }
	bool operator<(H o) const { return get() < o.get(); }
};

//This is the base of the hash 
static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok)


struct HashInterval {
    // Constructs the hashes of all substrings of a string implicitly
    // The hash of the string s[0]s[1] ... s[l - 1] is 
    // C^(l-1)s[0] + C^(l-2) s[1] + C^(l-3)s[2] + ... s[l - 1]
	vector<H> ha, pw;
	HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
		pw[0] = 1;
		rep(i,0,sz(str))
			ha[i+1] = ha[i] * C + str[i],
			pw[i+1] = pw[i] * C;
	}
    // The hash of the substring s[a : b - 1] is constructed as follows:
    // hash(s[0 : b - 1]) = C^(b - 1)s[0] + C^(b - 2)s[1] + ... C^(b - 1 - a)s[a] + C^(b-1-a-1)s[a-1] ... s[b-1]
    // hash(s[0 : a - 1]) = C^(a - 1)s[0] + ... s[a - 1]
    // hash(s[a : b - 1]) = C^(b - 1 - a)s[a] + C^(b-1-a-1)s[a-1] ... + s[b-1]
	H hashInterval(int a, int b) { // hash [a, b)
        return ha[b] - ha[a] * pw[b - a];
	}
};

vector<H> getHashes(string& str, int length) {
	if (sz(str) < length) return {};
	H h = 0, pw = 1;
	rep(i, 0, length)
		h = h * C + str[i], pw = pw * C;
	vector<H> ret = {h};
	rep(i,length,sz(str)) {
		ret.push_back(h = h * C + str[i] - pw * str[i-length]);
	}
	return ret;
}

H hashString(string& s){H h{}; for(char c:s) h=h*C+c;return h;}

const ll MOD = 1e9 + 7;
//The direct comparability of array hashes and string hashes is a concern that I have 

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    string t;
    cin >> t;
    HashInterval h(t);
    int k;
    cin >> k;
    vector<string> d(k); 
    rep(i, 0, k) cin >> d[i];
    map<int, set<ull>> hashes;
    rep(i, 0, k) hashes[sz(d[i])].insert(hashString(d[i]).x);
    // debug(hashes);
    // for(auto &[l, s] : hashes){
    //     cout << l <<":\n";
    //     for(auto x : s) cout << x << ", ";
    //     cout <<"\n";
    // }
    debug(sz(hashes));
    int n = sz(t);
    vll dp(n + 1);
    dp[0] = 1;
    rep(i, 1, n + 1){
        for(auto& [l, s] : hashes) if(i >= l){
            ull curr = h.hashInterval(i - l, i).x;
            // cerr << i << " " << l << " " << curr << "\n";
            if(s.find(curr) != s.end()) dp[i] = (dp[i] + dp[i - l])%MOD; 
        }
    }
    cout << dp[n];
}