As you might already know, Ada the Ladybug is a farmer. She grows lychee tree. Unlike a cherry tree, lychee tree really forms a tree (obviously a rooted tree - in node 0). The lychee fruits grow in bunches (there are (usualy) multiple lychee fruits in each node).

Ada will give you many queries, for harvesting lychees, consisting of 3 numbers: index of node U, I^th ancestor, L new lychees, meaning, that she wants to harvest lychees of I^th ancestor of node U. Afterward L new lychee fruits will grow on the node.

She wants you to sum all those harvest-values and output the sum. Value of harvest can be counted as X*W, where X is number of node where you'll harvest and W is the number of lychees in it.

Also note that input's format won't be easy (as usual). You will be given description of the tree and x₀, a, b. The next term could be counted as x_i=(a*x_i-1+b)%MOD, where % means modulo and MOD is equal to 10^9+7 (1000000007)

Firstly, you can set the number of lychees on each node: The number of lychee fruits on node i is equal to x_i%100003 (10⁵+3). Afterward there will be Q queries, giving you U, I, L (denoting XT as next x_i), U=XT%N, I=XT%(D[U]+1) (where D indicates DEPTH - root has depth 0), L=XT%100003 [priority of XT is from left to right].

NOTE: Parent of every node will always have lesser ID than the node itself (since the lychees far away from root are much more juicy).

Input

The first line contains five integers N, Q, x_i, a, b: 1 ≤ N ≤ 2*10⁵, 1 ≤ Q ≤ 4*10⁷, 0 ≤ a, b, x₀ < 1000000007

The next N-1 lines contains two integers 0 ≤ a < b < N, the branch connecting two nodes.

Output

Print a single line - the number sum of values over all queries.

Example Input

5 3 1 1 1
0 1
1 2
0 3
2 4

Example Output

13

Additional Information

#LYCHEES: 1 2 3 4 5
QUERY 1: 1 1 8
QUERY 2: 4 2 11
QUERY 3: 2 1 14

Example Input 2

5 5 2 3 4
0 1
1 2
2 3
2 4

Example Output 2

113299

Additional Information 2

#LYCHEES: 2 10 34 106 322
QUERY 1: 0 0 8746
QUERY 2: 2 1 36188
QUERY 3: 1 0 77101
QUERY 4: 4 2 81719
QUERY 5: 0 0 26368

Example Input 3

10 100 666 561 14159
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9

Example Output 3

9060951

Example Input 4

20 10000 30355495 415740782 580959825
0 1
1 2
2 3
3 4
3 5
0 6
6 7
7 8
8 9
3 10
1 11
3 12
11 13
3 14
3 15
4 16
16 17
8 18
17 19

Example Output 4

1939449924