题目描述

小明正在打游戏。

这是一个逃亡游戏，地图里有 $n$ 个补给站，由 $n-1$ 条道路将这些补给站连通，故该地图形成了一棵树。游戏会选择地图一个叶子并将其标记为出口，小明将从 $1$ 号补给站进入地图，并一路逃到出口去，中途不走回头路（不然还能叫逃亡游戏吗）。

每个补给站有一个强度为 $x_i$ 的补给，每当小明经过一个补给站时，小明就可以选择进行补给或者忽略它。小明通过他多年的游玩经验得知，他必须在离开地图前恰好 $k$ 个补给站进行补给（可以在出口补给站和入口补给站补给），才能顺利逃亡，补给少了会导致能量不够，而补给多了又会导致时间不够。但是，游戏有一个惩罚机制，如果小明在之前进行过一次补给，设其强度为 $a$，则之后所有的补给强度都必须不大于 $a$，若一个补给站的补给强度大于 $a$，则小明不能在这个补给站补给。

为了提高难度，游戏不会在一开始告诉小明出口具体是哪个节点，而是在小明每次到达一个补给站并决定是否进行补给之后，告诉小明出口位于该补给站的哪个儿子方向（设 $1$ 为根），这将让决策变得更加困难。不过好就好在，游戏一开始就会告诉小明所有的 $x_i$，以供小明思考策略。小明的策略很简单：提前选好一些补给站，在经过其中的补给站时必定进行补给，并保证对于每个叶子作为出口的情况均能满足所有条件。容易发现这是所有确定性策略中的最优策略。

不出意外地，小明作为老玩家已经玩腻了，于是他开始追求数学上的乐趣。他想知道有多少种确定将要进行补给的补给站的方案，使得不管出口是哪个叶子，他都能稳定获胜。并且，他查阅代码得知，每个补给站的 $x_i$ 是在游戏开始时选定的，其取值范围是 $[L_i,R_i]\cap Z$（选定后将会告诉小明），于是他想要你求出对于所有可能的地图局面，选取补给站集合方案的数量总和。

当然小明注意到在可以直接数学计算的一些情况中，方案数会是天文数字，于是他会让你输出其对 $1004535809$ 取模后的结果。

输入格式

第一行两个正整数 $n,k$，表示补给站的数量和需要进行的补给次数。

第二行 $n$ 个正整数 $L_i$，表示每个补给站补给强度的下限。

第三行 $n$ 个正整数 $R_i$，表示每个补给站补给强度的上限。

之后的 $n-1$ 行，每行两个正整数 $u,v$，表示一条树边。

输出格式

一行一个非负整数，表示方案数总和对 $1004535809$ 取模的结果。

输入输出样例

样例1输入

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

样例1输出

152

其余样例见下发文件，分别满足与测试点 $6,8,18,21$ 相同的限制。

数据范围

对于 $100\%$ 的数据，$1\le n\le200,1\le k\le20,1\le L_i\le R_i\le10^9$。保证输入的图是一棵树。

由于本题时限过大，相同限制的测试点将捆绑为一个子任务进行测试，且有极大的合理子任务依赖。