暂无测试数据。

有一棵 $n$ 个节点的无根树，刚开始树上每个节点的权值均为 $0$。KK 想对这棵树进行一些修改，他会任选一个节点作为初始的当前节点，然后重复以下动作:

1. 将当前节点 $i$ 的权值修改为一个正整数 $x$，需满足 $l_i \le x \le r_i$。其中 $l_i,r_i$ 是输入中给出的两个正整数。
2. 结束修改过程，或移动到一个与当前节点相邻的权值为 $0$ 的节点（如果不存在这样的节点，则必须结束修改过程）。

现在 KK 有两个问题：

1. 在修改结束后，可以得到多少棵不同的树，满足树上非零权值的最大值和最小值的差小于等于 $K?$ 其中 $K$ 是输入中给出的一个正整数。
2. 这些满足条件的树的权值之和为多少？（树的权值定义为这棵树上所有节点的权值之和）

你需要输出这两个问题的答案模 $10^9 + 7$。我们认为两棵树不同当且仅当至少存在一个节点的权值不同。

温馨提示：

1. KK 至少会修改一个节点（初始节点）。
2. 实质上 KK 会修改树上的任意一条路径，最后需要满足这条路径上的点的权值最大值和最小值之差小于等于 $K$。

输入格式

第一行两个正整数 $n$，$K$，表示节点数和权值差的最大值。

接下来 $n$ 行，每行两个正整数 $l_i,r_i$，表示第 $i$ 个节点修改后权值的最小值和最大值。

接下来 $n-1$ 行，每行两个正整数 $u_i, v_i$，表示节点 $u_i$ 和 $v_i$ 之间有一条边。数据保证形成一棵树。

输出格式

输出两行，每行一个整数，分别表示第一问和第二问的答案模 $10^9 + 7$ 的值。注意，如果你不打算回答第二问，请在第二行任意输出一个整数。如果输出文件只有一行，则会因格式不符合要求被判 $0$ 分。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le li \le ri \le 10^9$，$1 \le K \le 10^9$。

特殊限制 A：所有点构成一条链, 编号为 $i$ 的点和编号为 $i + 1$ 的点之间有连边

评分方式

本题共 $10$ 个测试点，每个测试点 $10$ 分。其中回答正确第一问可得 $7$ 分，回答正确第二问可得 $3$ 分。

由于本系统不支持 subtask，因此必须完全正确才能获得对应测试点的全部分数。

3 1
2 3
3 5
4 6
1 2
1 3

14
78

5 1
3 6
1 6
1 4
3 5
2 8
2 1
3 2
4 2
5 2

185
1753

200 381
158 1907
618 858
268 1493
307 899
224 1094
938 1558
104 1336
1022 1394
104 1358
938 1769
752 1717
341 1760
827 1643
1010 1189
867 1912
1147 1387
275 900
189 941
157 1384
293 1049
1151 1912
264 1263
1113 1506
783 850
800 1849
49 1807
492 1716
49 1609
109 1362
587 1046
292 1879
105 1593
843 1533
608 969
1090 1316
381 1228
607 1645
503 1658
158 1678
480 959
763 1677
921 1191
1100 1898
99 1135
497 1249
360 1613
517 855
931 1323
370 1691
375 1222
364 1631
581 1884
56 1203
933 1148
647 1280
1060 1937
381 1950
376 1269
586 1866
307 851
765 1253
847 1060
390 1486
769 1174
607 1489
276 1116
27 1826
954 1557
826 1356
1106 1509
493 1117
179 1277
366 1082
1160 1573
1062 1422
248 800
846 1462
352 829
721 1733
607 1108
1021 1801
790 1161
794 1759
236 1781
1117 1621
488 1961
936 1655
124 1232
795 978
56 1678
642 1690
317 1690
33 1358
1050 1105
929 1304
428 1009
163 1818
1005 1159
1009 1126
613 1783
470 1851
648 1665
111 1795
1119 1421
799 1235
206 1178
154 819
876 1613
239 915
849 1507
147 1021
558 1865
594 1361
487 1421
201 1878
178 1425
888 1606
291 840
955 1951
215 1996
306 892
408 963
492 1882
1092 1399
318 1052
716 968
384 1078
981 990
178 1039
696 905
810 1133
899 979
568 1097
1038 1151
347 1000
54 1703
714 1067
873 1106
785 1352
47 857
1101 1138
1029 1613
1181 1221
246 1482
856 1390
142 1367
1161 1559
1065 1460
808 851
383 1240
665 1327
528 1460
908 992
964 1759
953 1854
499 1381
1004 1544
813 914
305 953
529 1167
198 1528
284 1343
260 1890
1186 1652
967 1846
316 1731
547 1540
581 1587
703 1100
556 959
393 859
768 856
526 923
645 968
877 1427
157 1869
108 1107
22 1056
941 1076
505 955
72 896
235 1150
547 841
163 1286
64 849
691 1766
1023 1778
1115 1794
434 1314
58 1461
386 1389
873 1130
1149 1948
352 1465
447 1653
862 1168
839 1061
702 1750
85 1844
1141 1305
2 1
3 1
4 1
5 1
6 4
7 6
8 4
9 7
10 8
11 10
12 10
13 12
14 13
15 14
16 14
17 3
18 17
19 17
20 18
21 19
22 20
23 21
24 22
25 23
26 25
27 25
28 27
29 27
30 28
31 30
32 31
33 32
34 32
35 33
36 35
37 35
38 36
39 37
40 39
41 40
42 40
43 41
44 43
45 43
46 44
47 45
48 47
49 48
50 48
51 36
52 50
53 51
54 53
55 53
56 54
57 56
58 56
59 58
60 59
61 59
62 60
63 62
64 63
65 64
66 64
67 65
68 67
69 67
70 69
71 70
72 71
73 72
74 72
75 73
76 75
77 75
78 77
79 78
80 78
81 80
82 81
83 82
84 83
85 51
86 84
87 85
88 87
89 87
90 89
91 89
92 91
93 78
94 93
95 33
96 94
97 95
98 96
99 98
100 98
101 100
102 100
103 101
104 103
105 103
106 104
107 105
108 106
109 108
110 109
111 109
112 111
113 111
114 113
115 6
116 115
117 116
118 117
119 118
120 119
121 119
122 121
123 121
124 123
125 124
126 124
127 125
128 126
129 127
130 128
131 129
132 131
133 131
134 132
135 134
136 30
137 135
138 136
139 138
140 139
141 140
142 141
143 141
144 142
145 143
146 145
147 145
148 147
149 148
150 149
151 149
152 151
153 152
154 152
155 154
156 154
157 155
158 156
159 158
160 159
161 159
162 160
163 143
164 163
165 163
166 165
167 165
168 138
169 168
170 169
171 170
172 171
173 172
174 173
175 174
176 175
177 176
178 176
179 178
180 178
181 179
182 180
183 182
184 183
185 183
186 185
187 185
188 186
189 188
190 189
191 190
192 190
193 191
194 192
195 193
196 194
197 196
198 197
199 197
200 199

987704149
4561095