填空题

方案数量

Question

有这样的一个方格游戏：这个游戏是这样的：

1.有个方格，方格内每一个位置都有一个数，代表到达这个点后拥有的能量。

2.初始的时候在左上角，并将左上角的值作为初始能量，终点为右下角的点。

3.每一步只能往下或者往右走，且走一步需要消耗点能量。不能在原地停留，即不会获得中间节点的能量并且能量不累计。

4.当你选择了一条可行的路径（这条路径消耗的能量不超过现有能量），你可以走到终点。

例如：

最开始在点，拥有的是点能量，蓝色的方格代表从起点出发步以内所能走到的点，假设我们第一次走到,则到达后能量变为点，那么接下来可以达到的点为和。

现在想问你有多少条不同的路径（两条路径如果按顺序依次到达的点有一个不同，则认为是不同的路径方式）可以从左上角的点走到右下角的点，由于答案很大，请答案对取余。

输入描述：

输入第一行有一个整数，代表接下来有组测试数据。

对于每一组测试数据第一行输入两个整数和，

代表方格的大小。接下来行，每一行输入个数，代表这个方格内的能量。

保证每一个文件内和的总和不超过

输入样例： 2 3 3 2 1 1 1 1 1 1 1 1 6 6 4 5 6 6 4 3 2 2 3 1 7 2 1 1 4 6 2 7 5 8 4 3 9 5 7 6 6 2 1 5 3 1 1 3 7 2 输出描述： 对于每组数据输出一行，代表可以走到的方案数量。输出样例 10 3948