牛牛送快递
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

n个节点m条边的图，边的权值为组合数，从起点s到终点t的花费为路径上所有边的权值之积
求s到t的最小花费，由于答案可能很大请对取模。
示例1

输入

复制 
5,5,1,5,[[1,2,1,1],[1,5,5,3],[3,5,1,1],[2,4,1,1],[4,5,2,1]]

返回值

复制 
2

说明

1->2->4->5距离最短，为C_1^1*C_1^1*C_2^1=1*1*2=2

备注:

条城际高速的格式为 ，表示城市和城市之间有城际高速，通过该城际高速所需要的过路费为。数据保证和之间有通路。