Problem A
Stöðuflutningafylki

Búið til forrit sem þið getið notað til stöðuflutningafylkislausna í framhaldinu.

Stöðuflutningafylki $A$ gefur fjölda leiða til að komast frá einni stöðu í aðra. Til dæmis ef við höfum $5$ stöður þá er $a_{3,2}$ fjöldi leiða til að fara úr stöðu $3$ í stöðu $2$. Ef þetta er $0$ er engin leið.

Líta má á slíkt stöðuflutningafylki sem nágrannafylki á stefndu neti (sem er ekki endilega einfalt). Þá er verið að biðja um fjölda vega frá einhverjum leyfilegum upphafshnút í einhvern leyfilegan endahnút með nákvæmlega $k$ leggjum.

Inntak

Fyrsta lína inntaksins inniheldur þrjár jákvæðar heiltölur $n,m,k$. $n$ er fjöldi staða og uppfyllir $n\le 20$. $m$ er gildið sem mátta á úttakið við og uppfyllir $2\le m\le {10}^9+7$. $k$ er fjöldi skrefa sem á að taka og uppyfyllir $0\le k\le {10}^{18}$. Næst koma $n$ línur, hver með $n$ heiltölum aðskilin með bilum. Þessar línur gefa stöðuflutningafylkið, hver talnanna í fylkinu er eins stafa ekki neikvæð heiltala. Næsta lína gefur fjölda leyfilegra upphafsstaða $1\le s\le n$, og línan á eftir gefur þessar $s$ ólíku upphafsstöður. Næstu tvær línur gefa leyfilegar endastöður með sama hætti. Allar stöður eru táknaðar með heiltölu frá $0$ til $n-1$.

Úttak

Prentið fjölda leiða frá leyfilegri upphafsstöðu í leyfilega endastöðu með stöðuflutningafylkinu. Mátið svarið við $m$.

2 1000 10
1 1
1 0
1
1
2
0 1

89