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

备注:

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