水果家的背包
题号：NC222389
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给你一个容量大小为的背包，然后让你往背包里面放点东西，放什么呢？就放水果好了。

现在有一颗树，节点编号从到每个位置都有两种不同的水果，对于第个节点，第一种水果体积为w_i，个数为n_i，我们认为这n_i个水果完全相同；第二种水果体积为W_i，个数为N_i，同样的，我们认为这N_i个水果也是完全相同的。

现在我们认为每一个节点上的两种水果是互斥的，即 这两种水果可以都不选，也可以从这两种水果中选定一种，取若干个加入背包，但是不能同时选取两种水果。

现在需要进行次查询操作。

每次查询会给你两个参数，表示延树上从到的简单路径从走到，路过每个节点时你都可以选定该节点上的一种水果取若干个加入背包，但是不能超过背包容量的上限，当然你也可以两种水果都不拿，仅仅路过该节点。

对于每个查询的和你都需要求出对取余数后的结果，表示从一路走到，有多少种取水果的方案能够使得背包内所有水果的体积和恰好为。

输入描述:

第一行是两个正整数表示树的尺寸和查询的次数。
接下来行，每行四个正整数表示第个节点上两种互斥水果的体积和个数。
接下来来行，每行两个正整数表示树上一条连接两节点的边。
接下来行，每行两个正整数，表示一个查询。

输出描述:

对于每个查询，输出对取余数后的结果
示例1

输入

复制 
7 8
1 1 1000000000 1000000000
2 2 1000000000 1000000000
1 5 1000000000 1000000000
1 5 1000000000 1000000000
1 1 1000000000 1000000000
2 2 1000000000 1000000000
2 2 1000000000 1000000000
1 2
1 3
2 4
2 5
4 6
4 7
1 1
2 3
4 5
4 1
6 7
6 3
2 5
7 7

输出

复制 
3
216
216
216
405
6804
21
9

说明

样例解释：
查询树上从1到1的路径时，答案数组如下，{ans_k}表示从{u}一路走到{v}，有多少种取水果的方案能够使得背包内所有水果的体积和恰好为{k}。（下标从0开始计算，第一个数是{ans_0}，我们认为什么都不拿也是一种方案，所以{ans_0=1}）
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0....（后面都是0）
查询树上从2到3的路径时，答案数组如下：
1 2 3 4 5 6 5 4 3 2 1 0 0 0 0 0 0 0 0....（后面都是0）
查询树上从4到5的路径时，答案数组如下：
1 2 3 4 5 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0...（后面都是0）
查询树上从4到1的路径时，答案数组如下：
1 2 3 4 5 6 5 4 3 2 1 0 0 0 0 0 0 0 0....（后面都是0）
查询树上从6到7的路径时，答案数组如下：
1 1 3 3 6 6 7 7 6 6 3 3 1 1 0 0 0 0....（后面都是0）
查询树上从6到3的路径时，答案数组如下：
1 3 7 13 22 34 46 58 67 73 73 67 58 46 34 22 13 7 3 1 0 0 0 0 0....（后面都是0）
查询树上从2到5的路径时，答案数组如下：
1 1 1 1 1 1 0 0 0 0 0 0 0....（后面都是0）
查询树上7到7的路径时，答案数组如下：
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0....（后面都是0）
示例2

输入

复制 
1 1
1 5 2 2
1 1

输出

复制 
29

说明

答案数组如下：
1 1 2 1 2 1 0 0...（后面都是0）
示例3

输入

复制 
5 5
3 2 1 8
7 4 3 8
5 1 1000000000 8
9 4 7 7
3 5 8 10
2 4
2 3
4 1
4 5
4 3
3 4
2 1
5 3
4 3

输出

复制 
12800
12800
73130
245051
12800