CF486D Valid Sets

As you know, an undirected connected graph with $ n $ nodes and $ n-1 $ edges is called a tree. You are given an integer $ d $ and a tree consisting of $ n $ nodes. Each node $ i $ has a value $ a_{i} $ associated with it. We call a set $ S $ of tree nodes valid if following conditions are satisfied: 1. $ S $ is non-empty. 2. $ S $ is connected. In other words, if nodes $ u $ and $ v $ are in $ S $ , then all nodes lying on the simple path between $ u $ and $ v $ should also be presented in $ S $ . 3. . Your task is to count the number of valid sets. Since the result can be very large, you must print its remainder modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

N/A

N/A

In the first sample, there are exactly 8 valid sets: $ {1},{2},{3},{4},{1,2},{1,3},{3,4} $ and $ {1,3,4} $ . Set $ {1,2,3,4} $ is not valid, because the third condition isn't satisfied. Set $ {1,4} $ satisfies the third condition, but conflicts with the second condition.