#include<bits/stdc++.h>

using namespace std;

typedef unsigned int uint;

const int N=1e5+;

const uint mod=;

inline int read(){

    int x=,w=;char ch=;

    while(!isdigit(ch)) w|=ch=='-',ch=getchar();

    while(isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();

    return w?-x:x;

}

int f[N],sz[N],c[N][];

uint v[N],s[N],ml[N],ad[N];//int是会爆的

bool rv[N];

#define lc c[x][0]

#define rc c[x][1]

#define mul(x) x*=val,x%=mod

#define add(x) x+=val,x%=mod

//我习惯的写法是判断 not root

inline bool nrt(int x){return c[f[x]][]==x||c[f[x]][]==x;};

void pushup(int x){

    s[x]=(s[lc]+s[rc]+v[x])%mod;

    sz[x]=sz[lc]+sz[rc]+;

}

//自定义的优先级：乘法>加法>翻转

void Rev(int x){lc^=rc^=lc^=rc;rv[x]^=;};

void Mul(int x,uint val){mul(v[x]),mul(s[x]),mul(ml[x]),mul(ad[x]);}

void Add(int x,uint val){add(v[x]);add(ad[x]);val*=sz[x];val%=mod;add(s[x]);}

void pushdown(int x){

    if(ml[x]^) Mul(lc,ml[x]),Mul(rc,ml[x]),ml[x]=;

    if(ad[x]) Add(lc,ad[x]),Add(rc,ad[x]),ad[x]=;

    if(rv[x]) Rev(lc),Rev(rc),rv[x]=;

}

//以下跟普通的LCT没两样

int get(int x){return x==c[f[x]][];}

void link(int x,int y,int d){c[x][d]=y;f[y]=x;}

void rotate(int x){

    int y=f[x],z=f[y],d=get(x);

    if(nrt(y)) c[z][get(y)]=x;f[x]=z;

    //如果y=rt，说明y->z是一条虚边，也就是说x和z分属两棵不同的Splay，如果这样还连边z->x的话，后果emmm……

    //但x->z必须连，因为就算y是根，把x旋上去后x就成根了，而LCT中一棵Spaly的根的父边一定是一条虚边（原树的根所属的Splay除外），相当于x继承了y连虚边的使命。。。

    link(y,c[x][d^],d);

    link(x,y,d^);

    pushup(y),pushup(x);

}

int st[N],tp;

void splay(int x){

    int t=x;

    //手动用栈来pushdown

    st[tp=]=t;

    while(nrt(t)) st[++tp]=t=f[t];

    while(tp) pushdown(st[tp--]);

    for(;nrt(x);rotate(x)){

        int y=f[x];

        if(nrt(y)) get(x)^get(y)?rotate(x):rotate(y);

    }

}

void access(int x){

    for(int y=;x;x=f[y=x])

        splay(x),c[x][]=y,pushup(x);

}

void makert(int x){

    access(x),splay(x),Rev(x);

}

int findrt(int x){

    access(x),splay(x);

    while(lc) pushdown(x),x=lc;

    splay(x);return x;

}

void split(int x,int y){

    makert(x),access(y),splay(y);

}

void link(int x,int y){

    makert(x);if(findrt(y)^x) f[x]=y;

}

void cut(int x,int y){

    makert(x);

    //在这道题中由于保证了cut操作合法因此应该可以不加判断

    if(findrt(y)==x&&f[y]==x&&!c[y][]) f[y]=c[x][]=,pushup(x);

}

int n,m;

int main(){

    n=read(),m=read();

    for(int i=;i<=n;++i) v[i]=ml[i]=sz[i]=;

    for(int i=;i<n;++i) link(read(),read());

    char op[];int x,y;

    while(m--){

        scanf("%s",op);

        x=read(),y=read();

        switch(op[]){

            case '+':split(x,y);Add(y,read());break;

            case '-':cut(x,y);link(read(),read());break;

            case '*':split(x,y);Mul(y,read());break;

            case '/':split(x,y);cout<<s[y]<<endl;break;

        }

    }

    return ;

}