背景

什么是随机游走?随机游走一般需要至少3个人。所有人从起点开始游走,每次到达一个岔路口(设岔路口的个数为n),每个人就闭上眼睛,用手表示出一个0~n-1的数,把这些数加起来,再模n,得到的这个数即为他们选择的那个岔路口的编号。这样一来,这群人就可以随机地在这个城市游览(只要他们能记住回去的路>_<)。

当然,题目和随机游走没什么关系。。。

描述

Pear在一张有向图中,该有向图有N个节点。Pear从1号点出发,要求恰好在T时刻到达N号点。给定该有向图,请你求出Pear一共有多少种不同的路径。Pear不能在某个节点停留。若Pear从x号点到y号点需要花费t0单位的时间,那么他就必须花费t0单位的时间,不能多也不能少。

输入格式

第一行有两个数,N,T。

接下来N行,给出一个N*N的矩阵。第i行第j列的数若为0,则表示i号点到j号点没有边;若为1~9,则表示i号点到j号点所花费的时间。

输出格式

一行一个数,表示恰好在T时刻从1号点到N号点的路径(方法)数。由于这个数很大,请输出这个数除以10007的余数。

样例输入

样例一:

2 2

11

00

样例二:

5 30

12045

07105

47805

12024

12345

样例输出

样例一:

1

样例二:

7335

数据范围与约定

对于30%的数据,2≤N≤5,1≤T≤30

对于100%的数据,2≤N≤10,1≤T≤1000000000

样例解释

来源

做这道题请屏蔽搜索引擎和出CH外的其它OJ。

我会说这是原题么>_<