一方通行
题号:NC21481
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

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

输入

复制
2 2
1 2
2 1
1 2

输出

复制
6

备注:

1≤ n≤ 500, 1 ≤ k ≤ 13。