499 . 芽芽與圖
TopCoder
Description
芽芽收到一張 $N$ 個點（點的編號為 $1$ 到 $N$） $M$ 條邊的有向圖，圖沒有重邊，但可能有自環。此外，芽芽還會收到一個幸運數字 $L$
現在，對於每個點對 $(i, j)$，芽芽很好奇：從點 $i$ 出發，恰好經過 $L$ 條邊到點 $j$ 的方法數有多少種。由於方法數很大，請輸出這個數字 mod $10^9 + 7$ 後的結果。
兩個方法若為不同，代表存在一個 $i$，第一種方法的第 $i$ 條邊跟第二種方法的第 $i$ 條邊不一樣。
Input Format
輸入的第一行包含三個整數 $N, M, L (1 \leq N \leq 100, 0 \leq M \leq N^2, 1 \leq L \leq 10^9)$，代表芽芽收到的有向圖的點數、邊數，以及額外的幸運數字。
接下來的 $M$ 行，每行包含兩個數字 $x, y (1 \leq x, y \leq N)$，代表點 $x$ 跟點 $y$ 中間有一條有向邊。
保證輸入的圖沒有重邊，但圖可能有自環
Output Format
輸出 $N$ 行，每行輸出 $N$ 個以一個空白隔開數字，第 $i$ 行第 $j$ 個數字代表點 $i$ 經過恰好 $L$ 條邊到點 $j$ 的方法數。由於數字很大，請輸出 mod $10^9 + 7$ 後的結果。注意不要輸出行尾空白
Sample Input 1
4 7 3
1 1
1 2
2 3
3 4
4 1
1 3
4 2
1 1
1 2
2 3
3 4
4 1
1 3
4 2
Sample Output 1
2 2 2 2
1 1 0 0
1 1 2 0
1 1 2 2
1 1 0 0
1 1 2 0
1 1 2 2
Hints
Problem Source
NEOJ Problem 776
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測試資料 | 0 |
| 2 | 0~9 | 無特殊限制 | 100 |