ADALICI - Ada and Lychees

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 (usually) multiple lychee fruits in each node).

Ada will give you many queries, for harvesting lychees, consisting of 3 numbers: index of node U, Ith ancestor, L new lychees, meaning, that she wants to harvest lychees of Ith 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 x0, a, b. The next term could be counted as xi=(a*xi-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 xi%100003 (105+3). Afterward there will be Q queries, giving you U, I, L (denoting XT as next xi), 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, xi, a, b: 1 ≤ N ≤ 2*105, 1 ≤ Q ≤ 4*107, 0 ≤ a, b, x0 < 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

Added by:Morass
Date:2017-08-03
Time limit:9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2017-08-03 14:07:39
@[Rampage] Blue.Mary: I've modified (drastically) time limit. Your solution seems to be correct (good complexity) ~ so I admit it shall pass. Hope the time-limit won't allow more naive approaches. I'm not much sure why is your solution so slow even though the complexity is good [imho it might be problem with caching, since the arrays are BIG - but I might be wrong :/ ] ... anyway some modification shall make it pass [maybe resubmiting / other C languages / swapping "fat" dimensions] (I didn't wan't to increase it too much so it might be tight). Sorry for the inconvenience - and wishing you good day!


~/Morass
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.