k-Tree
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
不久之前，一位有创意的学生 Lesha 上了一堂有关树的课程。课堂结束后，Lesha 受到启发，想出了自己的一种树，这种树他称为 -树。
-树是一种无限的有根树，具有以下特性：
- 每个顶点恰好有 个子节点；
- 每条边都有一个权值；
- 对于从某个顶点出发连向其各个子节点的 条边，它们的权值分别为 。
下图展示了 -树的一部分。
当 Lesha 的好朋友 Dima 得知这种树后，马上产生了疑问：“从 -树的根出发，路径权值之和为 ，且路径上至少包含一条权值不少于 的边，这样的路径有多少条？”请帮助 Dima 求出答案。由于方案数可能非常大，请输出对 （）取模后的结果。
输入格式
一行包含三个用空格分隔的整数 、 和 （；）。
输出格式
输出一个整数，表示满足条件的路径数对 取模的结果。
3 3 2
3
3 3 3
1
4 3 2
6
4 5 2
7