「朝辞白帝彩云间，千里江陵一日还。两岸猿声啼不住，轻舟已过万重山。」
—— 李白《早发白帝城》
40 年走来不易，但发展永无止境。今天，中国因为在基础设施建设上的建树，被戏称为「基建狂魔」。
在城市中，你可以看到在一定范围内总有道路正在施工。
假定一个城市有 个关键站点，其中，有 对站点之间是有可能修建道路的，在第 对站点之间修建道路的代价为 。按照惯例，城市规划者需要用最少的代价修建 条道路，使得这些站点之间互相连通。而为了彰显我国的基础设施建设能力，你的任务是计算出总共有多少种修建道路的方案。
由于方案可能太多，以至于超出合理的范围，你只需要简单地输出方案数对 取模的答案。