路径积

题号：NC203503
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵n个节点的无根树(n个结点，n-1条边的无环连通图)，每个节点有一个权值 $a_i$

一共有m次查询，每次查询 $x_i$ 到 $y_i$ 的最短路径上所有点权的乘积。

为了防止答案过大，答案对1e9+7取模。

示例1

输入

复制

6,2,[1,2,3,4,5,6],[1,2,2,4,4],[2,3,4,5,6],[3,6],[5,5]

返回值

复制

[120,120]

说明

3到5的最短路径为3->2->4->5，路径积为3*2*4*5=120
6到5的最短路径为6->4->5，路径积为6*4*5=120

备注:



第一个参数n代表节点个数
第二个参数m代表查询次数
第三个参数vector a代表每个节点的权值
第四、五个参数vector u,v各自包含n-1个元素代表树上的边，与相连
第六、七个参数vector x,y各自包含m个元素，代表查询到的最短路径上的点权乘积

对于每个查询，答案存储在vector中并按照查询的时间顺序输出