Background

Wolfycz really likes the Fibonacci sequence (just kidding).

Problem Description

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.

Input Format

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$.

Output Format

For each Q x y query, output the answer.

5 10
2 1
1 3
2 4
5 2
Q 1 5
U 1 1
Q 1 1
Q 1 2
Q 1 3
Q 1 4
Q 1 5
U 2 2
Q 2 3
Q 4 5

0
1
2
2
4
4
4
10

Hint

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