sol.py

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)

while True:
    try:
        nave, bilhete = (int(x) for x in input().split(' '))
        S, T = (int(x) for x in input().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 = input().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)
    except:
        break