2049: 弗洛伊德（加强版）
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：10
题目描述
题目同P1932。数据范围不同。
-----------------------------------------------我是华丽的分割线-----------------------------------------------
弗洛伊德是一个大牛！给一个有向图G，他有n个结点，现在请你求出对于他的每一对结点（x,y），从x出发走恰好k条边以后恰好到达结点y的路径条数。
输入
输入文件第一行包含两个正整数n,k。（1<=n<=50,1<=k<2^31）
接下来n行，每行n个用空格隔开的数。若第i行第j个数为1，则表示i到j在G中有一条边直接相连，若为0，则没有边直接相连。
输出
输出文件包含n行，每行n个用空格隔开的数。表示从i出发走恰好k条边到达j的方案数。为了避免数字太大，请将所有数对8000取模。
样例输入 复制
2 1
0 1
1 0
样例输出 复制
0 1
1 0提示
考虑lg级别的算法。^_^