We have met so many problems on the tree, so today we will have a simple problem on a tree.
You are given a tree (an acyclic undirected connected graph) with nodes. The tree nodes are numbered from to . Each node has a weight . We will have four kinds of operations on it and you should solve them efficiently. Wish you have fun!

输入描述:

The first line of the input gives the number of test case,  ().  test cases follow.
For each case, the first line contains only one integer .() The next  lines each contains two integers ,  which means there is an edge between them. It also means we will give you one tree initially. 
The next line will contains  integers which means the initial weight  of each node. ()
The next line will contains an integer . () The next  lines will start with an integer 1, 2, 3 or 4 means the kind of this operation.
1.Given three integers , , , for the ,  and all nodes between the path from  to  inclusive, you should update their weight to . (, )
2.Given three integers , , ,  for the ,  and all nodes between the path from  to  inclusive, you should increase their weight by . (, )
3. Given three integers , , , for the ,  and all nodes between the path from  to  inclusive, you should multiply their weight by . (, )
4.Given two integers , , you should check the node weights on the path between  and , and you should output cubic sum of them. It means, output ,  is node on the path from  to  (inclusive  and ). ()

输出描述:

For each test case, output one line containing ``Case #x:'', where x is the test case number (starting from 1).
For operation 4, output a single integer in one line representing the result. The result could be huge, print it module 1,000,000,007.

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

Case #1:
100
8133
20221