B.迷路的Domen

題目敘述

寫完了2048，獨自在資訊社的Domen全然不知道外頭發生的事，當他一踏出資訊社這強大的屏障後，立刻受困於某個邪惡魔法陣中。

每當他走到大門時，就會有一位黑影把他拉回資訊社門口，不讓他離開。在Domen煩惱之際，資訊社社部傳來一個神祕的聲音：「如果想突破這個古老的魔法陣，就必須剛好經過K個景點到達校門口，否則將永遠受困於此......」於是Domen趕緊下載他網站上的一中校園地圖，經過他的研究後，他發現兩景點間可以直接走過去的路徑方法數是不一樣的，且去跟回程也有不同的方法數，所以Domen很好奇他從資訊社到校門口有多少種方法能使它經過K個景點，景點可以重複經過，只要有一種方法能走到下一景點就算是經過一景點。當然大門口也是一個景點的。

不過Domen很害怕路上遇到危險，他在一中校園穿梭時，不可以只把路走到一半就回頭，這樣很可能會受到其他魔法的詛咒。

輸入說明

有多筆測資，每筆測資第一行有4個數字：$N,S,E,K$，代表有$N$個景點，編號由$0$至$N-1$，資訊社社部編號為$S$，大門編號為$E$，以及限制要恰走$K$步。

接下來有$N$行，每行有$N$個數字，代號為$a$，第$i$行第$j$個數字表示由景點$i$至$j$有幾種不同的走法。

注意$a_{ij}$未必等於$a_{ji}$。

保證：

$1\leq N \leq 100$
$0\leq a_{ij} \leq 50$
$0 \leq K \leq 1000000$
不超過10筆測資

輸出說明

請輸出資訊社社部恰K步走到大門有幾種方法。如果答案太大，請出輸出除以10009之餘數即可。

範例輸入

範例輸出

By LFsWang 2014.05

Judge Setting

run-time limit: 1500 ms
memory limit: 65536 byte
測資數量: 0