Accelerator发现LastOrder被原先的实验员带走了,现在Accelerator要找出Lastorder,在此之前,他需要计算出实验员可能的逃跑路线。
学园都市的地图可以看成 3 棵 n 个点的树的结构,第 1 棵树的任意一个点到第 2 棵树上的任意一个点都有一条连边,第 2 棵树上的任意一个点到第 3 棵树的任意一个点都有一条连边,第 1 棵树上的任意一个点到第 3 棵树的任意一个点都有一条连边, 实验员一开始可能在任意一棵树的任何位置,他的油量只能支持他走 k 个点 (包括初始点),为了避免暴露,实验员不可能连续走两条跨越树的边,第一步和最后一步也不会走跨越树的边,而且其一定会沿着一条简单路径走完 k 个点。现在 Accelerator想要求出实验员可能的路径总数,由于答案很大,只需要输出对 998244353 取模后的结果即可。
输入描述:
第一行两个数 n, k。
接下来 n - 1 每行两个数 x, y 表示第一棵树有一条边连接 x, y 。
接下来 n - 1 每行两个数 x, y 表示第二棵树有一条边连接 x, y 。
接下来 n - 1 每行两个数 x, y 表示第三棵树有一条边连接 x, y 。
输出描述:
一个数,表示可能的路径总数对 998244353 取膜后的结果。
备注:
1≤ n≤ 500, 1 ≤ k ≤ 13。