路径数量
题号:NC18355
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

给出一个 n * n 的邻接矩阵A.
A是一个01矩阵 .
A[i][j]=1表示i号点和j号点之间有长度为1的边直接相连.
求出从 1 号点 到 n 号点长度为k的路径的数目.

输入描述:

第1行两个数n,k (20 ≤n ≤ 30,1 ≤ k ≤ 10)
第2行至第n+1行,为一个邻接矩阵

输出描述:

题目中所求的数目
示例1

输入

复制
4 2
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

输出

复制
2

说明

样例如图:
第一条路径:1-2-4
第二条路径:1-3-4