#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define add(x,y) x=(x+y)%mod;

#define mul(x,y) x=1ll*x*y%mod;

const int mod = ;

int  n,q,fa[],son[][],sum[],siz[];

int cola[],colm[],a[],r[];

inline void up(int x){

    sum[x]=(sum[son[x][]]+sum[son[x][]]+a[x])%mod;

    siz[x]=(siz[son[x][]]+siz[son[x][]]+)%mod;

}

inline void rev(int x){swap(son[x][],son[x][]);r[x]^=;}

inline void doa(int x,int y){

    add(a[x],y);

    add(sum[x],1ll*siz[x]*y%mod);

    add(cola[x],y);

}

inline void dom(int x,int y){

    mul(a[x],y);

    mul(sum[x],y);

    mul(cola[x],y);

    mul(colm[x],y);

}

inline void pd(int x){

    if(colm[x]!=){

      dom(son[x][],colm[x]);

      dom(son[x][],colm[x]);

      colm[x]=;

    }

    if(cola[x]){

      doa(son[x][],cola[x]);

      doa(son[x][],cola[x]);

      cola[x]=;

    }

    if(r[x]){

      if(son[x][])rev(son[x][]);

      if(son[x][])rev(son[x][]);

      r[x]=;

    }

}

inline bool notroot(int x){return x==son[fa[x]][]||x==son[fa[x]][];}

inline void push_all(int x){if(notroot(x))push_all(fa[x]);pd(x);}

inline int gs(int x){return son[fa[x]][]==x;}

inline void rot(int x){

    int y=fa[x],z=fa[y],b=gs(x),c=gs(y),d=son[x][!b];

    if(notroot(y))son[z][c]=x;

    fa[x]=z;

    if(d)fa[d]=y;

    son[y][b]=d;

    son[x][!b]=y;

    fa[y]=x;

    up(y),up(x);

}

inline void splay(int x){

    push_all(x);

    while(notroot(x)){

      int y=fa[x],z=fa[y];

      if(notroot(y)){

          if(gs(x)==gs(y))rot(y);

            else rot(x);

      }

      rot(x);

    }

}

inline void access(int x){

    for(int y=;x;y=x,x=fa[x])

      splay(x),son[x][]=y,up(x);

}

inline void makeroot(int x){

    access(x);

    splay(x);

    rev(x);

}

inline int findroot(int x){

    access(x);

    splay(x);

    while(son[x][])pd(x),x=son[x][];

    return x;

}

inline void spt(int x,int y){

    makeroot(x);

    access(y);

    splay(y);

}

inline void link(int x,int y){

    makeroot(x);

    if(findroot(y)!=x)fa[x]=y;

}

inline void cut(int x,int y){

    makeroot(x);

    if(findroot(y)==x&&fa[x]==y&&(!son[x][]))

      fa[x]=son[y][]=,up(y);

}

int main(){

    int i,j,k;

    scanf("%d%d",&n,&q);

    for(i=;i<=n;i++)siz[i]=sum[i]=a[i]=;

    for(i=;i<n;i++){

      int x,y;

      scanf("%d%d",&x,&y);

      link(x,y);

    }

    for(i=;i<=q;i++){

      char s[];

      int x,y,z,w;

      scanf("%s",s);

      if(s[]=='+'){

          scanf("%d%d%d",&x,&y,&z);

          spt(x,y);

          doa(y,z);

      }else if(s[]=='-'){

          scanf("%d%d%d%d",&x,&y,&z,&w);

          cut(x,y);

          link(z,w);

      }else if(s[]=='*'){

          scanf("%d%d%d",&x,&y,&z);

          spt(x,y);

          dom(y,z);

      }else {

          scanf("%d%d",&x,&y);

          spt(x,y);

          printf("%d\n",sum[y]);

      }

    }

    return ;

}