君は一昨日、友人のトウサから一つ、頼み事をされた。なんでも、木に等差数列を飾って誕生日パーティーに使いたいのだが、木が大きすぎて一人ではとてもできないのだという。そこで、優秀なプログラマである君に、効率的に木に等差数列を飾るプログラムを書いてもらいたいそうだ。君とトウサは旧知の親友である。君はトウサの頼み事を受けることにした。
飾り付けをする$N$ノードの木が与えられる。木のノードには$0$から$N-1$までの番号が振られている。最初、木のノードの点数は全て$0$である。プログラムは、以下の二つのクエリに対応しなければならない。
トウサの誕生日を祝うために、木を美しく飾ろう。
入力は以下の形式で与えられる。
$N$ $Q$
$A_0$ $B_0$
$A_1$ $B_1$
:
$A_{N-2}$ $B_{N-2}$
$COM_0$
$COM_1$
:
$COM_{Q-1}$
木のノード数$N$とクエリの数$Q$が$1$行に与えられる。続いて$N-1$行に木の辺の情報が与えられる。$A_i$,$B_i$は、ノード$A_i$と$B_i$の間に直接辺があることを示している。その後、$Q$個の命令$COM_j$が与えられる。
$COM_j$の形式は以下の通りである。
$0$ $S$ $T$
$S$、$T$は頂点の番号である。区間の指定は二つのノードによって行われる。$S$から$T$までの最短経路が指定された区間である。区間に含まれているノードに書かれた点数の総和を報告する。ただし、$S$と$T$も区間に含む。答えは非常に大きくなることがあるので、$10^9+7$で割ったあまりを出力すること。
$1$ $S$ $T$ $K$ $M$
上と同じく、$S$と$T$で指定された区間に含まれているノードに点数を足す。足す点数は、$S$からの最短距離を$L$として、以下のように算出される。
$K+L{\times}M$
入力は以下の条件を満たす。
$0$のクエリのとき、指定された区間に含まれているノードに書かれた点数の総和を一行に出力する。
3 3 0 2 1 2 1 1 0 0 1 0 0 2 0 0 1
3 3
まず、$1-2-0$の区間に初項$0$、公差$1$の数列を足す。ノードの点数は$0,1,2$の順に$2,0,1$となる。
次に、$0-2$の区間のノードの点数の和を出力する。$2+1=3$なので、$3$を出力する。
次に、$0-2-1$の区間のノードの点数の和を出力する。$2+1+0=3$なので、$3$を出力する。
5 6 1 0 2 0 3 2 4 1 1 1 4 0 4 0 4 1 1 3 0 7 3 0 2 2 1 4 1 8 0 0 4 2
4 10 43