SP32223 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 (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 $ _{0} $ , 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 $ ^{5} $ +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).

The first line contains five integers **N, Q, x $ _{i} $ , a, b: 1** The next **N-1** lines contains two integers **0 , the branch connecting two nodes.**

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