gistfile1.cpp

#include <stdio.h>
#include <iostream>

using namespace std;

#define MAX 112
#define P 10000

void identidade(int A[MAX][MAX]) {
  int i, j;
  for (i = 0; i < MAX; i++)
    for (j = 0; j < MAX; j++) 
    	A[i][j] = ((i == j));
}

void multmat(int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX]) {
  int i, j, k;
  for (i = 0; i < MAX; i++)
    for (j = 0; j < MAX; j++)
      for (C[i][j] = 0, k = 0; k < MAX; k++){ 
      	C[i][j] += A[i][k] * B[k][j]; 
      	C[i][j] %= P; 
      }
}

void expbin(int A[MAX][MAX], int n, int B[MAX][MAX]) {
  int C[MAX][MAX];
  if (n == 0){ 
  	identidade(B); 
  	return; 
  }
  if (n & 1){ 
  	expbin(A, n - 1, C); 
  	multmat(C, A, B); 
  	return; 
  }
  expbin(A, n >> 1, C); 
  multmat(C, C, B);
}

int main(){
	
	int N, L, S, T, i, j, x;
	int Ad[MAX][MAX], res[MAX][MAX];
	
	while(cin >> N){
	
		scanf("%d%d%d",&L,&S,&T);
		
		for(i=0;i<N;i++)for(j=0;j<N;j++)Ad[i][j]=0;
	
		for(i=0;i<N;i++){
			for(j=0;j<4;j++){
				cin >> x;
				Ad[i][x-1]+=1;
			}
		}
	
		expbin(Ad, L, res);
		
		printf("%d\n",res[S-1][T-1] % P);
		
	}
	
	return 0;
}