【题目背景】
We could have had it all. . . . . .
我们本该，拥有一切
Counting on a tree. . . . . .
何至于此，数数树上
Counting on a Tree（ CoaT）即是本题的英文名称。
【题目描述】
AccessGlobe最近正在玩一款战略游戏。在游戏中，他操控的角色是一名C国士兵。他的任务就是服从指挥官的指令
参加战斗，并在战斗中取胜。C国即将向D国发动一场秘密袭击。作战计划是这样的：选择D国的s个城市，派出C国
战绩最高的s个士兵分别秘密潜入这些城市。每个城市都有一个危险程度di，C国指挥官会派遣战绩最高的士兵潜入
所选择的城市中危险程度最高的城市，派遣战绩第二高的士兵潜入所选择的城市中危险程度次高的城市，以此类推
（即派遣战绩第i高的士兵潜入所选择城市中危险程度第i高的城市）。D国有n个城市，n-1条双向道路连接着这些
城市，使得这些城市两两之间都可以互相到达。为了任务执行顺利，C国选出的s个城市中，任意两个所选的城市，
都可以不经过未被选择的城市互相到达。AccessGlobe操控的士兵的战绩是第k高，他希望能估计出最终自己潜入的
城市的危险程度。AccessGlobe假设C国是以等概率选出任意满足条件的城市集合S，他希望你帮他求出所有可能的
城市集合中，AccessGlobe操控的士兵潜入城市的危险程度之和。如果选择的城市不足k个，那么AccessGlobe不会
被派出，这种情况下危险程度为0。当然，你并不想帮他解决这个问题，你也不打算告诉他这个值除以998,244,353
的余数，你只打算告诉他这个值除以64,123的余数。
BZPRO