import java.io.*;
import java.util.*;

//Задача "Встретиться в середине"
//8-я Интернет-олимпиада сезона 2008-2009, усложненый уровень
//Автор задачи:  Максим Буздалов, buzdalov@rain.ifmo.ru
//Автор решения: Максим Буздалов, buzdalov@rain.ifmo.ru

//Рещение с целочисленным переполнением.

public class mitm_mb_wa1 {
    private static void myAssert(String msg, boolean exp) {
        if (!exp) {
            System.err.println(msg);
            System.exit(-1);
        }
    }

    static int n, m, a, b, x, p;
    static int[][] nWays;
    static int[] endsCurr;
    static int[] endsNext;
    static int noAB;

    private static void fillNumberOfWays(int[][] ways, int fromVertex, boolean strict) {
        if (strict) {
            ways[fromVertex][0] = 1;
        } else {
            Arrays.fill(ways[fromVertex], 1);
        }
        int maxMask = ways[0].length;
        for (int mask = 0; mask < maxMask; ++mask) {
            int ecCurr = 0;
            int ecNext = 0;
            for (int ends = 0; ends < noAB; ++ends) {
                if (((1 << ends) & mask) == 0) {
                    endsNext[ecNext++] = ends;
                } else {
                    endsCurr[ecCurr++] = ends;
                }
            }
            endsCurr[ecCurr++] = fromVertex;

            for (int iNext = 0; iNext < ecNext; ++iNext) {
                int next = endsNext[iNext];
                int nMask = mask | (1 << next);
                long dest = ways[next][nMask];
                for (int iCurr = 0; iCurr < ecCurr; ++iCurr) {
                    int curr = endsCurr[iCurr];
                    int nw = nWays[curr][next];
                    int fromv = ways[curr][mask];
                    /**
                     * Integer overflow is here
                     */
                    dest += nw * fromv;
                }
                dest %= p;
                ways[next][nMask] = (int) dest;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new File("mitm.in"));

        /**
         * Reading the number of vertices, edges, start & end vertices,
         * meeting edge.
         */
        n = in.nextInt();
        m = in.nextInt();
        a = in.nextInt();
        b = in.nextInt();
        x = in.nextInt();
        p = in.nextInt();

        myAssert("n is out of bounds", 2 <= n && n <= 20);
        myAssert("m is out of bounds", 1 <= m && m <= 200);
        myAssert("a is out of bounds", 1 <= a && a <= n);
        myAssert("b is out of bounds", 1 <= b && b <= n);
        myAssert("a == b", a != b);
        myAssert("x is out of bounds", 1 <= x && x <= m);
        myAssert("p is out of bounds", 2 <= p && p <= 1000000000);

        --a;
        --b;
        --x;

        /**
         * This array changes vertex indices so that A and B become
         * two last indices.
         * This will help to decrease time and memory consumption
         * as many as 4 times.
         */
        int[] reindex = new int[n];
        for (int i = 0, j = 0; i < n; ++i) {
            if (i != a && i != b) {
                reindex[i] = j++;
            }
        }
        reindex[a] = n - 2;
        reindex[b] = n - 1;
        a = n - 2;
        b = n - 1;

        /**
         * Reading the indicence matrix. We count the number of ways
         * to walk from i to j, so summing up.
         */
        nWays = new int[n][n];
        int meetSource = -1;
        int meetTarget = -1;
        for (int i = 0; i < m; ++i) {
            int source = in.nextInt();
            int target = in.nextInt();
            myAssert((i + 1) + ": source is out of bounds", 1 <= source && source <= n);
            myAssert((i + 1) + ": target is out of bounds", 1 <= target && target <= n);
            myAssert((i + 1) + ": source == target", source != target);
            source = reindex[source - 1];
            target = reindex[target - 1];
            ++nWays[source][target];
            ++nWays[target][source];
            if (i == x) {
                meetSource = source;
                meetTarget = target;
            }
        }
        in.close();

        /**
         * These arrays will be used to store the possible
         * current end vertices and next end vertices
         * for the specified mask
         * in subset dynamic programming induction step.
         */
        endsCurr = new int[n];
        endsNext = new int[n];

        noAB = n - 2;

        /**
         * fromA[subset][endVertex] is the number of ways to walk from A to endVertex
         * using __exactly__ the specified subset of vertices (A is included implicitly, endVertex is included explicitly).
         * Note that B is not included in the possible vertex sets, because it mustn't be there.
         */
        int[][] fromA = new int[n][1 << noAB];
        fillNumberOfWays(fromA, a, true);

        /**
         * fromB[subset][endVertex] is the number of ways to walk from B to endVertex
         * using __some of__ the specified subset of vertices (B is included implicitly, endVertex is included explicitly).
         * Note that A is not included in the possible vertex sets, because it mustn't be there.
         */
        int[][] fromB = new int[n][1 << noAB];
        fillNumberOfWays(fromB, b, false);

        /**
         * Merging the results.
         */
        int all = (1 << noAB) - 1;
        long answer = 0;
        int[] fromAS = fromA[meetSource];
        int[] fromAT = fromA[meetTarget];
        int[] fromBS = fromB[meetSource];
        int[] fromBT = fromB[meetTarget];
        for (int subsetForA = 0; subsetForA <= all; ++subsetForA) {
            long fromAtoS = fromAS[subsetForA];
            long fromAtoT = fromAT[subsetForA];
            int subsetForB = all & ~subsetForA;
            long fromBtoS = fromBS[subsetForB];
            long fromBtoT = fromBT[subsetForB];
            answer += fromAtoS * fromBtoT;
            answer += fromAtoT * fromBtoS;
            answer %= p;
        }

        PrintWriter out = new PrintWriter("mitm.out");
        out.println(answer);
        out.close();
    }
}
