fibonacci

题目背景

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$询问,输出其答案

输入输出样例

输入样例 #1

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

输出样例 #1

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