Cuvinte10

#include<iostream>
#include<cstring>
#include<cassert>
#define DIM 300005
#define mod 1000000007
using namespace std;
int n, m, k, i, j, sum, sol, x, sumlen, maxim;
char s[DIM];
int ff[DIM], d[DIM], e[DIM];
struct trie{
    int t, len;
    trie *f[26];
    trie(){
        t = 0;
        len = 0;
        for(int i = 0; i < 26; i++){
            f[i] = NULL;
        }
    }
};
trie *r;
void adauga(trie *r, char *s){
    if(*s == 0){
        r->t = 1;
    }
    else{
        if(r->f[*s - 'a'] == NULL){
            r->f[*s - 'a'] = new trie();
            r->f[*s - 'a']->len = r->len + 1;
        }
        adauga(r->f[*s - 'a'], s + 1);
    }
}
void dfs(trie *r){
    if(r->t == 1){
        d[r->len]++;
        return;
    }
    e[r->len]++;
    for(int i = 0; i < 26; i++){
        if(r->f[i] != NULL){
            dfs(r->f[i]);
        }
    }
}
int main(){
    r = new trie();
    cin>> n >> m >> k;
    for(i = 1; i <= n; i++){
        cin>> s;
        adauga(r, s);
    }
    dfs(r);
    for(i = 1; i <= m; i++){
        cin>> x;
        ff[x]++;
    }
    sum = sol = 1;
    for(i = 1; i <= 300000; i++){
        sum = sum * 1LL * k % mod;
        sum = (sum - d[i] + mod) % mod;
        for(j = 1; j <= ff[i]; j++){
            sol = sol * 1LL * (sum - e[i] + mod) % mod;
            sum = (sum - 1 + mod) % mod;
        }
    }
    cout<< sol <<"\n";
    return 0;
}