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