题目背景

Wolfycz 很喜欢 Fibonacci 数列（雾

题目描述

Wolfycz 热衷于研究 Fibonacci 数列，他定义 $Fib_i$ 为Fibonacci 数列的第 $i$ 项，同时定义 $Fib_0=0,Fib_1=1$，并且对于任意的$i$，满足 $Fib_i=Fib_{i-1}+Fib_{i-2}$。

Wolfycz 也喜欢植树，有一天他植了一颗滑稽树（就是 OI 中所说的树，$n$ 个点，$n-1$ 条边，以 $1$ 为根），初始时树上的节点都没有滑稽果，于是 Wolfycz 不惜花重金购入了金坷垃，每次他给滑稽树上的节点 $x$ 施肥 $k$ 克，会使 $x$ 以及它的子树都长出一堆滑稽果，具体来讲，如果 $x$ 子树中的某个节点距离 $x$ 的距离为 $D$，那么这个节点就会长出 $Fib_{D+k}$ 个滑稽果

Wolfycz 觉得滑稽树上滑稽果已经够多了，因此他想 Van 游戏，所以他会时不时询问你两个节点路径上有多少个滑稽果。

输入格式

第一行给出两个整数 $N,M$，表示树的节点个数和操作个数

第 $2\sim N$ 行，第 $i$ 行两个数 $x,y$，表示节点 $x,y$ 之间有一条边

接下来 $M$ 行，每行一个形如 U x k 或 Q x y 的形式

• U x k：$x$ 的子树内的节点，若其到 $x$ 的距离为 $D$，则该点长出 $Fib_{D+k}$ 个滑稽果，$x$ 也要长滑稽果
• Q x y：询问路径 $x,y$ 上所有节点的滑稽果个数和（包括 $x,y$），答案对 $10^9+7$ 取模

输出格式

对于每个 Q x y 询问，输出其答案。

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

提示

对于$30\%$的数据，$N,M,k\leqslant 10^3$

对于$100\%$的数据，$N,M\leqslant 10^5$，$1\leqslant x,y\leqslant N$，$1\leqslant k\leqslant 10^{18}$。