这是一个关于蚂蚁的游戏。在这个游戏中，你拥有一个 $N$ 行 $M$ 列的网格。行号从上到下编号为 $1$ 到 $N$，列号从左到右编号为 $1$ 到 $M$。网格中的每个单元格都有无限量的某种糖果，每单位糖果会给玩家提供特定的分数。游戏只有 1 个步骤：放置 1 只超级蚂蚁在网格中的任意单元格，蚂蚁将执行其神奇的工作来决定你的得分。

一旦超级蚂蚁被放置在某个单元格中，它就会执行一种系统性的行为来从存储中收集糖果单位。如果没有剩余时间，蚂蚁会从其所在单元格的存储中获取 1 单位糖果并停止工作。如果有剩余时间，它会开始一种神奇的操作，即蚂蚁克隆操作。超级蚂蚁会根据当前剩余时间开始向所有可能的单元格克隆自己（所有的克隆操作同时开始）。克隆到距离为 $D$ 的单元格需要 $D$ 秒。位于 $(R_1, C_1)$ 的蚂蚁与位置 $(R_2, C_2)$ 的距离为 $\max(|R_1 - R_2|, |C_1 - C_2|)$（其中 $|X|$ 表示 $X$ 的绝对值）。一旦新的超级蚂蚁被克隆出来，它就会利用剩余时间像超级蚂蚁一样行动。

最后，当剩余时间不足以让任何蚂蚁克隆到任何其他单元格时，每只蚂蚁都会从其所在单元格收集一个单位的糖果，你的得分是所有收集到的糖果单位价值的总和。注意，蚂蚁不能克隆到距离超过当前剩余时间的单元格，蚂蚁不能多次克隆到同一个单元格，它不能克隆到自己所在的单元格，并且任何单元格在任何时候都可以包含任意数量的蚂蚁。

那么，蚂蚁可以克隆到哪些位置呢？首先，蚂蚁不能克隆到网格之外的单元格。其次，它只能克隆到其 8 个方向向量上的任意单元格。方向向量意味着同一方向上的所有连续单元格，例如从位置 $(A, B)$ 出发，东向向量将生成 $(A, B + 1), (A, B + 2), (A, B + 3)$ 等等。在下图中，一只剩余时间为 2 秒的超级蚂蚁可以克隆到 16 个位置，其中 8 个距离为 1，8 个距离为 2。

给定网格中每个糖果单位的得分值、你拥有的总允许时间（时间从第一只蚂蚁被放置时开始）以及第一只超级蚂蚁的起始单元格，你能编写一个程序来计算如果你使用该单元格所能获得的得分吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来是各个测试用例，每个测试用例的第一行包含 3 个由空格分隔的整数 $N, M, S$（$1 \le N, M \le 50$ 且 $0 \le S \le 500$），分别表示网格的行数、列数和剩余时间。接下来的一行包含 2 个由空格分隔的整数 $I, J$（$1 \le I \le N$ 且 $1 \le J \le M$），表示第一只蚂蚁起始的行号和列号。随后是 $N$ 行，每行包含 $M$ 个由空格分隔的整数，表示该行每个单元格中糖果单位的价值。网格中的每个整数不小于 0 且不大于 9。

输出格式

对于每个测试用例，打印一行，包含一个整数，表示游戏结束时你将获得的得分。由于结果可能非常大，请输出其对 $1,000,000,007$ ($10^9 + 7$) 取模的结果。

样例

输入 1

2
5 6 1
3 3
0 2 4 6 8 1
1 1 2 3 1 2
1 4 5 6 3 4
2 7 8 9 5 8
3 5 8 0 7 0
5 6 2
3 3
0 2 4 6 8 1
1 1 2 3 1 2
1 4 5 6 3 4
2 7 8 9 5 8
3 5 8 0 7 0

输出 1

45
349

说明

在第一个样例中，第一只蚂蚁将从其单元格收集一个价值为 5 的糖果单位。此外，它将在 8 个方向上克隆出 8 只蚂蚁，它们每只只能从各自的单元格中获得 1 个糖果单位。总得分为 $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45$。

在第二个样例中，第一只蚂蚁将克隆自己到距离为 2 的 8 个单元格（剩余时间为 0），以及距离为 1 的 8 个单元格（剩余时间为 1，因此后者的每个克隆体将进一步克隆自己）。