你有一棵树。这棵树上深度为 的点是根节点，深度为 的点是叶子节点。每个非叶子节点都有恰好 个子结点。树上连接两个节点的边都有边权，每个点连向其第 个子结点的边的边权恰好为 。
以下是一个 的例子。
给定一个常数 ，求有多少条从根出发到任意一点的简单路径，满足：
这条路径上经过的边权总和为 ；
这条路径上至少有一条边的边权为 。
答案对 19491001 取模。
输入一行三个整数 。
仅一个整数，表示答案对 19491001 取模后得到的值。
4 3 2
2
201 502 10
14440881
对于所有数据，满足：。
