P5138 fibonacci

Wolfycz really likes the Fibonacci sequence (just kidding).

Wolfycz is keen on studying the Fibonacci sequence. He defines $Fib_i$ as the $i$-th term of the Fibonacci sequence, and defines $Fib_0=0,Fib_1=1$. For any $i$, it satisfies $Fib_i=Fib_{i-1}+Fib_{i-2}$. Wolfycz also likes planting trees. One day he planted a “funny tree” (that is, the tree in OI: $n$ nodes, $n-1$ edges, rooted at $1$). Initially, none of the nodes on the tree had any funny fruits. Then Wolfycz spent a lot of money to buy fertilizer. Each time he fertilizes a node $x$ on the tree with $k$ grams, node $x$ and its entire subtree will grow a bunch of funny fruits. Specifically, if a node in the subtree of $x$ has distance $D$ to $x$, then this node will grow $Fib_{D+k}$ funny fruits. Wolfycz thinks there are already enough funny fruits on the tree, so he wants to play a game, and he will occasionally ask you how many funny fruits there are on the path between two nodes.

The first line contains two integers $N,M$, representing the number of nodes in the tree and the number of operations. Lines $2$ to $N$ each contain two integers $x,y$, indicating that there is an edge between nodes $x$ and $y$. Next come $M$ lines, each in the form `U x k` or `Q x y`. - `U x k`: For each node in the subtree of $x$, if its distance to $x$ is $D$, then it grows $Fib_{D+k}$ funny fruits. Node $x$ also grows fruits. - `Q x y`: Query the sum of funny fruits on all nodes along the path from $x$ to $y$ (including $x$ and $y$). Output the answer modulo $10^9+7$.

For each `Q x y` query, output the answer.

For $30\%$ of the testdata, $N,M,k\leqslant 10^3$. For $100\%$ of the testdata, $N,M\leqslant 10^5$, $1\leqslant x,y\leqslant N$, $1\leqslant k\leqslant 10^{18}$. Translated by ChatGPT 5