#include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cstdio>

 using namespace std;

 const int D=;

 char in[D],out[*],*I=in,*O=out;

 #define gc (*I++)

 #define pc(x) ((*O++)=x)

 template <typename Q>

 void gt(Q&x) {

     static char c,f;

     for(c=gc,f=;!isdigit(c);c=gc)if(c=='-') f=;

     for(x=;isdigit(c);c=gc) x=x*+c-'';

     f && (x=-x);

 }

 template <typename Q>

 void pt(Q x){

     static char stk[];

     static int top;

     top=;

     if(x==) pc('');

     for(;x;x/=) stk[++top] = x%+'';

     for(;top;top--) pc(stk[top]);

 }

 typedef unsigned ll;

 const int Maxn=,Mod=;

 int n,m;

 ll w[Maxn],tagm[Maxn],taga[Maxn],sz[Maxn];

 int ch[Maxn][],p[Maxn],flip[Maxn],sum[Maxn];

 void update(int x){

     if(x==) return;

     int&l=ch[x][],&r=ch[x][];

     sum[x] = (sum[l] + sum[r] + w[x])%Mod;

     sz[x] = (sz[l] + sz[r] + )%Mod;

 }

 void add_tag(int x,ll a,ll m){

     if(!x) return;

     sum[x] = (sum[x]*m+a*sz[x])%Mod;

     w[x] = (w[x]*m+a)%Mod;

     tagm[x] = tagm[x]*m%Mod;

     taga[x] = (taga[x]*m+a)%Mod;

 }

 /*void tag_mul(int x,ll _v) {

     (sum[x]*=_v)%=Mod;

     (w[x]*=_v)%=Mod;

     (tagm[x]*=_v)%=Mod;

     (taga[x]*=_v)%=Mod;

 }

 void tag_add(int x,ll _v) {

     (sum[x]+=(sz[x]*_v)%Mod)%=Mod;

     (w[x]+=_v)%=Mod;

     (taga[x]+=_v)%=Mod;

 }*/

 bool isroot(int x) {

     return ch[p[x]][]!=x && ch[p[x]][]!=x;

 }

 void down(int x) {

     int &l=ch[x][],&r=ch[x][];

     if(flip[x]) {

         swap(l,r);

         flip[l]^=;

         flip[r]^=;

         flip[x]=;

     }

     /*if(tagm[x]!=1) {

         for(int i=0;i<2;i++)if(ch[x][i])tag_mul(ch[x][i],tagm[x]);

         tagm[x]=1;

     }

     if(taga[x]!=0) {

         for(int i=0;i<2;i++)if(ch[x][i])tag_add(ch[x][i],taga[x]);

         taga[x]=0;

     }*/

     ll&a=taga[x],&m=tagm[x];

     if(a!= || m!=) {

         add_tag(l,a,m);

         add_tag(r,a,m);

         a=;m=;

     }

 }

 void rotate(int x){

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

     int l=ch[y][]==x,r=l^;

     if(!isroot(y)){

         ch[z][ch[z][]==y]=x;

     }

     p[y]=x;

     p[ch[x][r]]=y;

     p[x]=z;

     ch[y][l]=ch[x][r];

     ch[x][r]=y;

     update(y);

 //    update(x);

 }

 int stk[Maxn],top;

 void splay(int x){

     stk[top=]=x;

     for(int t=x;!isroot(t);stk[++top]=t=p[t]);

     for(;top;top--) down(stk[top]);

     for(;!isroot(x);){

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

         if(!isroot(y)) {

             if( (ch[y][]==x) ^ (ch[z][]==y)) rotate(x);

             else rotate(y);

         }

         rotate(x);

     }

     update(x);

 }

 void access(int x) {

     for(int t=;x;x=p[t=x]){

         splay(x);

         ch[x][]=t;

         update(x);

     }

 }

 void newroot(int x) {

     access(x);

     splay(x);

     flip[x]^=;

 }

 inline void n_as(int u,int v){

     newroot(u);

     access(v);

     splay(v);

 }

 void Cut(int x,int y) {

     n_as(x,y);

     ch[y][]=p[x]=;

     update(x);

 }

 void Link(int x,int y) {

     newroot(x);

     p[x]=y;

 }

 int en[Maxn*],next[Maxn*],fir[Maxn];

 void Add(int from,int to) {

     static int tot=;

     en[++tot]=to;

     next[tot]=fir[from];

     fir[from]=tot;

 }

 void BFS(int u) {

     int *q=stk,ql=,qr=;

     q[++qr]=u;

     for(int x;ql<qr;){

         x=q[++ql];

         for(int k=fir[x];k;k=next[k]){

             int v=en[k];

             if(v==p[x]) continue;

             p[v]=x;

             q[++qr]=v;

         }

     }

 }

 void init(){

     gt(n),gt(m);

     for(int u,v,i=;i<n;i++) {

         gt(u),gt(v);

 //        Add(u,v),Add(v,u);

         Link(u,v);

     }

 //    BFS(1);

     tagm[]=;

     for(int i=;i<=n;i++) sz[i]=sum[i]=tagm[i]=w[i]=;

 }

 void work() {

     char c;

     ll u,v,d;

     /*printf("round%d:\n",0);

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

             printf("%d :p=%d,ch=(%d,%d),w=%d,taga=%d,tagm=%d\n",i,p[i],ch[i][0],ch[i][1],w[i],taga[i],tagm[i]);

         }*/

     for(int i=;i<=m;i++) {

         for(;;) {

             c=gc;

             if(c=='+') {

                 gt(u),gt(v),gt(d);

                 n_as(u,v);

 //                tag_add(v,d);

                 add_tag(v,d,);

                 break;

             }if(c=='-') {

                 gt(u),gt(v);

                 Cut(u,v);

                 gt(u),gt(v);

                 Link(u,v);

                 break;

             }if(c=='*') {

                 gt(u),gt(v),gt(d);

                 n_as(u,v);

                 add_tag(v,,d);

 //                tag_mul(v,d);

                 break;

             }if(c=='/'){

                 gt(u),gt(v);

                 n_as(u,v);

                 pt(sum[v]);

                 pc('\n');

                 break;

             }

         }

         /*printf("round%d:\n",i);

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

             printf("%d :p=%d,ch=(%d,%d),w=%d,taga=%d,tagm=%d,sum=%d\n",i,p[i],ch[i][0],ch[i][1],w[i],taga[i],tagm[i],sum[i]);

         }*/

     }

 }

 int main() {

 #ifdef DEBUG

     freopen("in.txt","r",stdin);

 //    freopen("out.txt","w",stdout);

 #endif

     fread(in,,D,stdin);

     init();

     work();

     return printf(out),;

 }