#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

ifstream in("problem5.in");
ofstream out("problem5.out");


namespace std {
    template<>
    struct hash<pair<int, char>>{
        size_t operator()(const pair<int, char>& s) const {
            return s.first + s.second;
        }
    };
    template<>
    struct hash<set<int>>{
        size_t operator()(const set<int>& s) const {
            //return s.empty()?0:*s.begin();
            return accumulate(s.begin(), s.end(), 0, [](int a, int b){ return (a << 1) + b; });
        }
    };
}
struct compSet{
    bool operator()(const set<int>& a, const set<int>& b) const {
        return (*a.begin()) == (*b.begin());
    }
};
ostream& operator<<(ostream&out, set<int> s){
    for_each(s.begin(), s.end(),[&out](int i){out << i << " ";});
    return out;
}

struct NFA{
    set<int> term;
    set<int> start;
    int size = 0;
    unordered_map<pair<int, char>, set<int>> trans;

    NFA reverse(){
        NFA r;
        r.start = term;
        r.term = start;
        r.size = size;

        for(auto f : trans) {
            int from = f.first.first;
            char c = f.first.second;
            for(auto to : f.second){
                r.trans[make_pair(to, c)].insert(from);
            }
        }
        return r;
    }
    set<int> genericTrans(set<int> s, char c){
        set<int> r;
        for(auto m : s) {
            auto it = trans.find(make_pair(m, c));
            if(it != trans.end()){
                r.insert(it->second.begin(),it->second.end());
            }
        }
        //cout << "GT " << s << " | " << c << " | " << r << "\n";
        return r;
    }
    bool terminal(set<int> s){
        for(auto i : s) {
            if(term.count(i)) return 1;
        }
        return 0;
    }
    int cnt = 0;
    unordered_map<set<int>, int> sets;
    bool add(set<int> s){
        if(s.empty()) return false;
        if(sets.count(s)) {return false; }
        sets[s] = ++cnt;
        return true;
    }
    void process(set<int> s){
        for(char c = 'a'; c <= 'z'; c++) {
            set<int> reachable = genericTrans(s, c);
            bool ok = add(reachable);
            if(ok) process(reachable);
        }
    }
    int transisitons() {
        int ret = 0;
        for (auto f : trans) {
            for (auto to : f.second) {
                ret++;
            }
        }
        return ret;
    }
    NFA determinize(){
        NFA r;
        cnt = 0;
        sets.clear();
        add(start);
        process(start);

        for(auto from : sets) {
            int fromi = from.second;
            for(char c = 'a'; c <= 'z'; c++) {
                auto to = genericTrans(from.first, c);
                if(to.empty()) continue;
                int toi = sets[to];
                r.trans[make_pair(fromi, c)].insert(toi);
            }
        }
        r.start = {sets[start]};
        for(auto s : sets) {
            if(terminal(s.first)) {
                r.term.insert(s.second);
            }
        }
        r.size = sets.size();
        r.target = target;
        return r;
    }

    set<int> delta(int s, char c){
        set<int> r;
        //for(auto m : s) {
            auto it = trans.find(make_pair(s, c));
            if(it != trans.end()){
                r.insert(it->second.begin(),it->second.end());
            }
        //}
        return r;
    }
    bool terminal(int s){
        //for(auto i : s) {
            if (term.count(s)) return 1;
        //}
        return 0;
    }

    int target = 0;

    #define INC(cnt) cnt = (cnt + 1) % (1000000007);
    #define ADD(a, b) ((a + b) % (1000000007));

    int count() {
        set<int> s = {1};
        set<int> ss;
        vector<uint64_t> count, count2;
        count.resize(size + 1);
        count2 = count;
        count[1] = 1;
        while(target--) {
            ss.clear();
            fill_n(count2.begin(), size + 1, 0);
            for(auto f : s) {
                for(char c = 'a'; c <= 'z'; c++) {
                    set<int> to = delta(f, c);
                    for_each(to.begin(), to.end(), [&count2, &count, &ss, &f](int i){count2[i] = ADD(count2[i], count[f]); if(!ss.count(i)) ss.insert(i); });
                }
            }
            count = count2;
            s = ss;
        }

        uint64_t cnt = 0;
        for(auto p : ss) {
            if(terminal(p)) cnt = ADD(cnt, count[p]);
        }

        return cnt;
    }

};

istream& operator>>(istream&in, NFA& aut){
    char c;
    int n,m,k,a,b;
    in >> n >> m >> k >> aut.target;
    while(k--){
        in >> a;
        aut.term.insert(a);
    }
    while(m--){
        in >> a >> b >> c;
        aut.trans[make_pair(a, c)].insert(b);
    }
    aut.size = n;
    aut.start.insert(1);
    return in;
}

ostream& operator<<(ostream&out, NFA s){
    out << s.size << " " << s.trans.size() << " " << s.term.size() << endl;
    out << s.term << "\n";
    for (auto f : s.trans) {
        for (auto to : f.second) {
            out << f.first.first << " " << to << " " << f.first.second << "\n";
        }
    }
    return out;
}

ostream& xd(ostream&out, NFA s){
    out << "digraph fa {" << endl;
    out << "rankdir = LR;" << endl;
    out << "node[shape=doublecircle];" << endl;
    for(auto t : s.term) {
        out << '"' << t << "\";" << endl;
    }
    out << "node[shape=circle];" << endl;
    for (auto f : s.trans) {
        for (auto to : f.second) {
            out << "\"" << f.first.first << "\"->\"" << to << "\"[label=\"" << f.first.second << "\"];" << "\n";
        }
    }
    out << "}";
    return out;
}

int main()
{
    //ifstream zin("/home/vladimir/src/lab/disc/2/I_NFA2DFA/fsa4.txt");
    NFA a;
    in >> a;
    //TODO: We have to remove useless states first
    auto b = a.determinize().count();
    out << b;
    //xd(out, b);
    out.close();
    return 0;
}