sol.py

import fileinput

MAX = 0
P = 10000


def identidade(matriz):
    for i in range(MAX):
        for j in range(MAX):
            matriz[i][j] = int((i == j))


def multmat(matrizA, matrizB, matrizC):
    for i in range(MAX):
        for j in range(MAX):
            k = 0
            matrizC[i][j] = 0
            while k < MAX:
                matrizC[i][j] += matrizA[i][k] * matrizB[k][j]
                matrizC[i][j] %= P
                k += 1


def expbin(matrizA, n, matrizB):
    matrizC = [[0 for i in range(MAX)] for j in range(MAX)]
    if n == 0:
        identidade(matrizB)
        return
    if n & 1:
        expbin(matrizA, n-1, matrizC)
        multmat(matrizC, matrizA, matrizB)
        return

    expbin(matrizA, n >> 1, matrizC)
    multmat(matrizC, matrizC, matrizB)


stdin = fileinput.input()
while True:
    line = stdin.readline().strip()
    if not line:
        break
    nave, bilhete = (int(x) for x in line.split(' '))
    S, T = (int(x) for x in stdin.readline().split(' '))

    MAX = nave

    m = [[0 for i in range(MAX)] for j in range(MAX)]
    res = [[0 for i in range(MAX)] for j in range(MAX)]

    for i in range(nave):
        l = stdin.readline().split(' ')
        for j in range(4):
            x = int(l[j])
            m[i][x-1] += 1

    expbin(m, bilhete, res)
    print(res[S-1][T-1] % P)