Problem: Problem

You were asked by your friend Tousa the day before yesterday. He wants to decorate a tree with an arithmetic progression and use it for a birthday party, but the tree is too big to be used alone. Therefore, he wants you, an excellent programmer, to write a program that efficiently decorates a tree with arithmetic progressions. You and Tousa are old friends. You decide to accept Tousa's request.

You will be given a tree of $ N $ nodes to decorate. The nodes of the tree are numbered from $ 0 $ to $ N-1 $. Initially, all tree nodes score $ 0 $. The program must respond to the following two queries:

* $ 0 $. Finds the sum of the points written on the nodes of the specified section of the tree.
* $ 1 $. Adds an arithmetic progression to the nodes in the specified section of the tree.



Beautifully decorate the trees to celebrate Tousa's birthday.

Constraints

The input satisfies the following conditions.

* All inputs are integers
* $ 1 \ le N, Q \ le 10 ^ 5 $
* $ 0 \ le A, B, S, T \ le N-1 $
* $ 0 \ le K, M \ le 10 ^ 5 $

Input

The input is given in the following format.


$ N $ $ Q $
$ A_0 $ $ B_0 $
$ A_1 $ $ B_1 $
::
$ A_ {N-2} $ $ B_ {N-2} $
$ COM_0 $
$ COM_1 $
::
$ COM_ {Q-1} $


The number of nodes in the tree $ N $ and the number of queries $ Q $ are given in the $ 1 $ row. Then the $ N-1 $ line is given information about the edges of the tree. $ A_i $, $ B_i $ indicate that there is an edge directly between the nodes $ A_i $ and $ B_i $. After that, $ Q $ instructions $ COM_j $ are given.


The format of $ COM_j $ is as follows.


$ 0 $ $ S $ $ T $


$ S $ and $ T $ are vertex numbers. The interval is specified by two nodes. This is the interval in which the shortest route from $ S $ to $ T $ is specified. Report the sum of the points written on the nodes included in the interval. However, $ S $ and $ T $ are also included in the interval. The answer can be very large, so print out the remainder divided by $ 10 ^ 9 + 7 $.



$ 1 $ $ S $ $ T $ $ K $ $ M $


As above, add points to the nodes included in the interval specified by $ S $ and $ T $. The points to be added are calculated as follows, assuming that the shortest distance from $ S $ is $ L $.



$ K + L {\ times} M $


Output

When querying $ 0 $, the sum of the points written in the nodes included in the specified interval is output in one line.

Examples

Input

3 3
0 2
1 2
1 1 0 0 1
0 0 2
0 0 1


Output

3
3


Input

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


Output

4
10
43

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

#define MOD 1000000007

struct TousaSegmentTree {
  int n;
  vector<ll> sum, lastval;
  vector<ll> rangeadd;
  TousaSegmentTree(int _n){
    n = 1;
    while(n<_n+1)n<<=1;
    sum.assign(2*n-1,0ll);
    lastval.assign(2*n-1,0ll);
    rangeadd.assign(2*n-1,0ll);
  }
  void push(int a, int b, int k){
    (sum[k] += (ll)(b-a) * (b-a+1) / 2 % MOD * rangeadd[k] % MOD) %= MOD;
    (lastval[k] += (ll)(b-a) * rangeadd[k]) %= MOD;
    if(k<n-1){
      (rangeadd[2*k+1] += rangeadd[k]) %= MOD;
      (rangeadd[2*k+2] += rangeadd[k]) %= MOD;
    }
    rangeadd[k] = 0;
  }
  void _add(int l, int r, ll x, int a, int b, int k){
    push(a,b,k);
    if(r<=a || b<=l)return;
    if(l<=a && b<=r){
      (rangeadd[k] += x) %= MOD;
      push(a,b,k);
    }else{
      int m = (a+b)/2;
      _add(l,r,x,a,m,2*k+1);
      _add(l,r,x,m,b,2*k+2);
      (sum[k] = sum[2*k+1] + sum[2*k+2] + lastval[2*k+1]*(b-m)) %= MOD;
      (lastval[k] = lastval[2*k+1] + lastval[2*k+2]) %= MOD;
    }
  }
  void addTousa(int l, int r, ll a, ll b){
    _add(l,l+1,a,0,n,0);
    _add(l+1,r,b,0,n,0);
    _add(r,r+1,MOD-(a+(r-l-1)*b)%MOD,0,n,0);
  }
  ll sumTousa(int l, int r, int a, int b, int k){
    push(a,b,k);
    if(r<=a || b<=l)return 0ll;
    if(l<=a && b<=r){
      return sum[k];
    }else{
      int m = (a+b)/2;
      ll lsum = sumTousa(l,r,a,m,2*k+1);
      ll rsum = sumTousa(l,r,m,b,2*k+2);
      int rcnt = max(0,min(r,b)-max(l,m));
      return (lsum + rsum + lastval[2*k+1]*rcnt) % MOD;
    }
  }
  ll sumTousa(int l, int r){
    return sumTousa(l,r,0,n,0);
  }
};

struct HeavyLightDecomposition {
  int n;
  vector<vector<int>> g;
  vector<int> depth, parent, csize;
  vector<vector<int>> chains;
  vector<int> chainid, chainpos;
  int root = 0;
  HeavyLightDecomposition(int _n){
    n = _n;
    g.resize(n);
    depth.assign(n,-1); parent.assign(n,-1); csize.assign(n,0);
    chainid.assign(n,-1); chainpos.assign(n,-1);
  }
  void add_edge(int a, int b){
    g[a].push_back(b);
    g[b].push_back(a);
  }
  void dfs(int p, int bef, int d){
    depth[p] = d;
    csize[p] = 1;
    for(int to : g[p])if(to!=bef){
      dfs(to, p, d+1);
      parent[to] = p;
      csize[p] += csize[to];
    }
  }
  void dfs2(int p, int bef, int id){
    chainid[p] = id;
    chainpos[p] = chains[id].size();
    chains[id].push_back(p);
    for(int to : g[p])if(to!=bef){
      if(csize[to]*2 >= csize[p]){
        // heavy
        dfs2(to, p, id);
      }else{
        // light
        chains.push_back(vector<int>());
        dfs2(to, p, chains.size()-1);
      }
    }
  }
  void construct(){
    dfs(root,-1,0);
    chains.push_back(vector<int>());
    dfs2(root,-1,0);
  }
  int lca(int a, int b){
    while(a != b){
      if(depth[a] < depth[b])swap(a,b);
      if(chainid[a] == chainid[b])return b;
      if(depth[chains[chainid[a]].front()] < depth[chains[chainid[b]].front()])swap(a,b);
      a = chains[chainid[a]].front();
      a = parent[a];
    }
    return a;
  }
};

int main(){
  int n,q;
  scanf("%d%d",&n,&q);
  HeavyLightDecomposition hld(n);
  REP(i,n-1){
    int a,b;
    scanf("%d%d",&a,&b);
    hld.add_edge(a,b);
  }
  hld.construct();

  vector<TousaSegmentTree> segs;
  REP(i,hld.chains.size()){
    segs.push_back(TousaSegmentTree(hld.chains[i].size()));
  }

  while(q--){
    int typ,s,t;
    scanf("%d%d%d",&typ,&s,&t);
    int lca = hld.lca(s,t);
    if(typ == 0){
      // sum
      ll ans = 0;
      while(true){
        int id = hld.chainid[s];
        if(id == hld.chainid[lca]){
          (ans += segs[id].sumTousa(hld.chainpos[lca], hld.chainpos[s]+1)) %= MOD;
          break;
        }
        (ans += segs[id].sumTousa(0, hld.chainpos[s]+1)) %= MOD;
        s = hld.chains[id].front();
        s = hld.parent[s];
      }
      while(true){
        int id = hld.chainid[t];
        if(id == hld.chainid[lca]){
          (ans += segs[id].sumTousa(hld.chainpos[lca]+1, hld.chainpos[t]+1)) %= MOD;
          break;
        }
        (ans += segs[id].sumTousa(0, hld.chainpos[t]+1)) %= MOD;
        t = hld.chains[id].front();
        t = hld.parent[t];
      }
      printf("%lld\n",ans);
    }else{
      // add
      ll a,b;
      scanf("%lld%lld",&a,&b);
      while(true){
        int id = hld.chainid[s];
        int r = hld.chainpos[s]+1;
        if(id == hld.chainid[lca]){
          int l = hld.chainpos[lca];
          segs[id].addTousa(l, r, (a+(r-l-1)*b)%MOD, MOD-b);
          (a += (r-l)*b) %= MOD;
          break;
        }
        segs[id].addTousa(0, r, (a+(r-1)*b)%MOD, MOD-b);
        (a += r*b) %= MOD;
        s = hld.chains[id].front();
        s = hld.parent[s];
      }
      int rest = hld.depth[t] - hld.depth[lca];
      (a += (rest-1)*b) %= MOD;
      b = MOD-b;
      while(true){
        int id = hld.chainid[t];
        int r = hld.chainpos[t]+1;
        if(t == lca)break;
        if(id == hld.chainid[lca]){
          int l = hld.chainpos[lca] + 1;
          segs[id].addTousa(l, r, (a+(r-l-1)*b)%MOD, MOD-b);
          break;
        }
        segs[id].addTousa(0, r, (a+(r-1)*b)%MOD, MOD-b);
        (a += r*b) %= MOD;
        t = hld.chains[id].front();
        t = hld.parent[t];
      }
    }
  }
  return 0;
}