#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

int n, m, a, b, x, p;
int mx[20][20];
int meet1, meet2;
bool used[20];

long long ans;

void go(int index, long long mul, bool met)
{
    if (!mul) 
    {
        return;
    }
    if (index == b)
    {
        if (met) 
        {
            ans = (ans + mul) % p;
        }
        return;
    }
    
    used[index] = true;
    
    if ((index == meet1 || index == meet2) && !used[meet1 + meet2 - index])
    {
        go(meet1 + meet2 - index, mul * mx[meet1][meet2], true);
    }
    else
    {
        for (int i = 0; i < n; ++i)
        {
            if (!used[i])
            {
                go(i, mul * mx[index][i], met);
            }
        }
    }
    
    used[index] = false;
}

int main()
{
    std::ifstream in("mitm.in");
    in >> n >> m >> a >> b >> x >> p;
    --a, --b, --x;
    for (int i = 0; i < m; ++i)
    {
        int src, trg;
        in >> src >> trg;
        --src;
        --trg;
        mx[src][trg]++;
        mx[trg][src]++;
        if (i == x)
        {
            meet1 = src;
            meet2 = trg;
        }
    }
    mx[meet1][meet2] = mx[meet2][meet1] = 1;

    go(a, 1, false);
    
    std::ofstream out("mitm.out");
    out << ans;
    
    return 0;
}
