当前没有测试数据。

题目描述

一年一度的圣诞节快到了，小 C 要在家门口准备一棵圣诞树。

这个圣诞树可以看成一个树结构，即由 n个点、n−1条边构成的一个连通图。

小 C 要在每个节点处放置一个铃铛。铃铛上写有一个 1 到 W 之间的正整数 x，其中 W 是小 C 预先给定的。

设第 i 个节点处的铃铛上的正整数为 $w_i$，对于树上所有的边 $(u,v)$，如果都满足 $∣w_u−w_v∣≤k$，那么称这棵圣诞树是优美的，其中 k 也是小 C 预先给定的。

现在小 C 想知道有多少种方案能得到优美的圣诞树。答案对 $10^9+9$ 取模。

输入格式

从文件 christmas.in 中读取数据。

第一行三个整数，分别为 n、k、W，n 表示树的大小，k、W如题所述；

接下来 n−1 行，每行两个数u、v，表示一条树边 (u,v)，描述了树的形态。

输出格式

输出到文件 christmas.out 中。

仅一行，一个数表示方案数对 $1000000009(=10^9+9)$取模的结果。

样例

5 1 3
1 2
1 3
2 4
2 5

103

10 2 4
1 2
1 3
1 4
3 5
3 6
4 7
4 8
2 9
5 10

379990

样例#3/4

见选手目录下的 christmas3/christmas4.in 和 christmas3/christmas4.ans。

样例三满足测试点 6∼9的条件。

样例四满足测试点 10∼15 的条件。

数据范围