SP11813 CNTPATHS - Count weighted paths

John 喜欢步行从家到大学，但他在离开后最多只能用 **T** 秒到达。我们可以用一幅有 **N** 个顶点的图来表示这个场景。图中的顶点 0 代表 John 的家，顶点 1 代表他的大学。顶点之间可以通过双向道路连接，每条道路需要不同的时间通过。 John 喜欢多样的路线。我们定义一条有效路径是以顶点 0（John 的家）为起点，并以顶点 1（他的大学）为终点的顶点序列。在这个序列中，每对连续顶点之间都有一条道路相连（注意，在路径中一个顶点可以多次出现）。John 穿过一条路径所花的时间是路径中所有道路时间的总和。请计算所有需要总时间最多为 **T** 秒的不同路径的数量。两条路径被认为是不同的，当且仅当它们在某个时刻访问了不同的顶点。 给定 **T**、**N** 和顶点之间的道路信息，你需要计算在最多 **T** 秒内可以走完的不同路径的数量。最终结果要对 1000000007（即 $10^9 + 7$）取模。

第一行包含一个整数 **TOTAL**，表示测试用例的数量（1 ≤ **TOTAL** ≤ 10）。 每个测试用例的第一行包含两个整数，分别是 **N** 和 **T**。（2 ≤ **N** ≤ 5，1 ≤ **T** ≤ 1000000000）。 接下来的 **N** 行表示从顶点 **i** 到其他顶点的道路信息。第 **i** 行由 **N** 个字符组成，索引从 **j** = 0 到 **N-1**。**i** 行中的第 **j** 个字符表示连接顶点 **i** 和 **j** 的道路。如果字符是 '-'，表示顶点 **i** 和 **j** 之间没有道路。否则，字符为 1、2 或 3，表示 John 从顶点 **i** 到顶点 **j** 所需的时间（单位为秒）。 对于每对顶点 (**i**, **j**)，顶点 **i** 和顶点 **j** 之间的道路字符和顶点 **j** 和顶点 **i** 之间的道路字符是相同的。 对于每个顶点 **i**，不会有连接顶点自身的道路。

对于每个测试用例，输出一行“Case #i: R”，其中 **R** 是从顶点 0 到顶点 1 在最多 **T** 秒内能够完成的有效路径总数。结果需对 1000000007 取模。 **本翻译由 AI 自动生成**