指定长度路径数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

题目给出一个有n个节点的有向图,求该有向图中长度为k的路径条数。方便起见,节点编号为1,2,…,n,用邻接矩阵表示该有向图。该有向图的节点数不少于2并且不超过500.

 

 

例如包含两个节点的有向图,图中有两条边1 → 2 ,2 → 1 。

长度为1的路径有两条:1 → 2 和 2 →1 ;

长度为2的路径有两条:1 → 2 → 1和2 → 1 → 2 ;

偷偷告诉你也无妨,其实这个图无论k取值多少 ( k > 0 ),长度为k的路径都是2条。

Input

多组输入,每组输入第一行是有向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。接下来一行是一个整数k.k小于30.

Output

输出一个整数,即为图中长度为k的路径的条数。

Sample Input

3
0 1 0
0 0 1
0 0 0
2

Sample Output

1

Hint

Source

归去识无路