#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
vector<int> putevi[500][500];
int main()
{
		freopen("obilazak.in", "r", stdin);
		freopen("obilazak.out", "w", stdout);
    int n,m,l,k,a,b;
    scanf("%i %i %i %i %i %i", &n, &m, &k, &l, &a, &b);
    for (int j = 0; j < m; j++)
    {
        int s, e, r;
        scanf("%i %i %i", &s, &e, &r);
        putevi[r][s].push_back(e);
    }
    int *prethodni = new int[n];
    int *trenutni = new int[n];
    memset(prethodni, 0, n*sizeof(int));
    memset(trenutni, 0, n*sizeof(int));
    prethodni[a]=1;
    for (int i = 0; i < l; i++)
    {
        int zeton;
        scanf("%i", &zeton);
        for (int j = 0; j < n; j++)
            if (prethodni[j] != 0)
            {
                for (vector<int>::const_iterator iter = putevi[zeton][j].begin(); iter != putevi[zeton][j].end(); ++iter)
                {
                    trenutni[*iter] += prethodni[j];
                    trenutni[*iter] %= 1000000;
                }
            }
        swap(prethodni, trenutni);
        memset(trenutni, 0, n*sizeof(int));
    }
    printf("%i\n", prethodni[b]);
		fclose(stdin);
		fclose(stdout);
    return 0;
}