#include <fstream>
//#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

using namespace std;
vector<vector<pair<int, int>>> aut; // aut[a] - из какого состояния; .first - в какое; .second - по какому символу
vector<bool> isTermin;
map<set<int>, vector<set<int>>> new_aut_with_sets; // new_aut[a][b] - переход из состояния a в b
map<set<int>, bool> new_isTermin_with_sets;
map<set<int>, map<int,int>> memoize;

int ans(const set<int>& curSost, int rest) {
    if (memoize[curSost].count(rest) != 0) {
        return memoize[curSost][rest];
    }
    int* cur = &memoize[curSost][rest];
    if (rest == 0) {
        *cur = (new_isTermin_with_sets[curSost]) ? 1 : 0;
        return *cur;
    }
    *cur = 0;
    for (const auto& next : new_aut_with_sets[curSost]) {
        *cur += ans(next, rest - 1);
        *cur %= 1000000007;
    }
    return *cur;
}

void getNewAut() {
    queue<set<int>> P;
    set<set<int>> Qd; // запоминает уже использованные множества
    P.push({1});
    Qd.insert({1});
    new_isTermin_with_sets[{1}] = isTermin[1];
    while (!P.empty()) {
        auto popped = P.front();
        P.pop();
        for (int i = 0; i < 26; ++i) {
            set<int> qd;
            for (int j : popped) { // бежим по удаленному из очереди множеству состояний
                for (auto z : aut[j]) { // получаем пары - в какое состояние по какому символу
                    if (z.second == i) {
                        qd.insert(z.first);
                    }
                }
            }
            if (qd.empty()) continue;
            if (Qd.count(qd) == 0) {
                P.push(qd);
                Qd.insert(qd);
                for (int j : qd) {
                    if (isTermin[j]) {
                        new_isTermin_with_sets[qd] = true;
                        break;
                    }
                }
            }
            new_aut_with_sets[popped].push_back(qd);
        }
    }
}

int main() {
    int n, m, k, len;
    ifstream cin("problem5.in");
    ofstream cout("problem5.out");
    cin >> n >> m >> k >> len;
    isTermin.resize(n + 1);
    aut.resize(n + 1);
    int a, b;
    char c;
    for (int i = 0; i < k; ++i) {
        cin >> a;
        isTermin[a] = true;
    }
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> c;
        aut[a].push_back(make_pair(b, c - 'a'));
    }
    getNewAut();
    cout << ans({1}, len);
    return 0;
}