路径的“长度”是路径中的边数。

给定一个源顶点和一个目标顶点，我想找到从源顶点到 给定长度* k 的目标顶点的 路径 数。 *

• 我们可以根据需要多次访问每个顶点，因此，如果从a到的路径b是这样的：a -> c -> b -> c -> b它被认为是有效的。这意味着可能会有周期，我们可以多次穿越目的地。

• 两个顶点可以通过多个边连接。因此，如果顶点a的顶点b是由两个边缘，则该路径连接，a -> b经由边缘1和a -> b经由边缘2被认为是不同。

• 顶点数N≤70，而路径长度K≤10 ^ 9。

• 由于答案可能非常大，因此将以某个数字为模进行报告。

到目前为止，我一直在想：

我们可以使用广度优先搜索而无需将任何顶点标记为已访问，在每次迭代中，我们都跟踪该路径所需的边数“ n_e”，并记录我们每个边的重复边数的 乘积 “
p”路径有。

如果n_e大于k，则搜索搜索应终止；如果到达n_e等于k 的目的地，则搜索将终止，并增加p路径数。

我认为我们可以使用深度优先搜索来代替广度优先搜索，因为我们不需要最短的路径，而广度优先搜索中使用的Q的大小可能还不够。

我正在考虑的第二种算法类似于使用这种方法的弗洛伊德·沃沙尔算法。只有我们不需要最短的路径，所以我不确定这是正确的。

我的第一个算法遇到的问题是’K’可以达到1000000000，这意味着我的搜索将一直运行直到它具有10 ^
9条边并且n_e边数在每个级别上仅增加1，这将非常速度很慢，而且我不确定是否会因大量输入而终止。

所以我需要一种不同的方法来解决这个问题。任何帮助将不胜感激。