#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#define int unsigned int

using namespace std;

int read(){

    int s=,t=;char c;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxn=,MOD=;

int n,Q,sum[maxn],A[maxn],B[maxn],g[maxn],a[maxn],sz[maxn],t[maxn][],f[maxn],N[maxn];

int M(int x){return x>=MOD?x-MOD:x;}

void up(int x){sum[x]=M(M(sum[t[x][]]+sum[t[x][]])+a[x]);sz[x]=sz[t[x][]]+sz[t[x][]]+;}

void modify_a(int k,int x){

    if(!k)return;

    a[k]=M(a[k]+x);

    sum[k]=M(sum[k]+sz[k]*x%MOD);

    A[k]=M(A[k]+x);

}//make 0 no influence

void modify_b(int k,int x){

    if(!k)return;

    a[k]=a[k]*x%MOD;

    sum[k]=sum[k]*x%MOD;A[k]=A[k]*x%MOD;B[k]=B[k]*x%MOD;

}

void down(int k){

    if(g[k]){

        swap(t[k][],t[k][]);

        if(t[k][])g[t[k][]]^=;

        if(t[k][])g[t[k][]]^=;

        g[k]=;

    }

    if(B[k]!=){

        modify_b(t[k][],B[k]);modify_b(t[k][],B[k]);

        B[k]=;

    }

    if(A[k]){

        modify_a(t[k][],A[k]);modify_a(t[k][],A[k]);

        A[k]=;

    }

}

bool isroot(int x){return !x||(t[f[x]][]!=x&&t[f[x]][]!=x);}

void rotate(int y){

    int x=f[y];

    int k=y==t[x][];

    t[x][!k]=t[y][k];f[t[y][k]]=x;

    if(!isroot(x))t[f[x]][x==t[f[x]][]]=y;f[y]=f[x];f[x]=y;

    t[y][k]=x;

    up(x);up(y);

}

void splay(int x){

    int top=x,tot=;N[]=x;

    while(!isroot(top))top=f[top],N[++tot]=top;

    for(int i=tot;i>=;i--)down(N[i]);

    while(!isroot(x)){

        if(isroot(f[x])){rotate(x);break;}

        int X=x==t[f[x]][],Y=f[x]==t[f[f[x]]][];

        if(X^Y)rotate(x),rotate(x);

        else rotate(f[x]),rotate(x);

    }

}

void access(int x){

    int y=;

    while(x){

        splay(x);

        t[x][]=y;

        up(x);///

        y=x;x=f[x];

    }

}

void reserve(int x){access(x);splay(x);g[x]^=;}

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

void find(int x,int y){reserve(x);access(y);splay(y);}

void cut(int x,int y){find(x,y);t[y][]=f[x]=;}

char s[];

#undef int

int main(){

#define int unsigned int

    n=read();Q=read();

    for(int i=;i<=n;i++)sum[i]=a[i]=,sz[i]=,A[i]=,B[i]=;

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

    while(Q--){

        scanf("%s",s);

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

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

            int z=read();

            find(x,y);modify_a(y,z);

        }

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

            int u=read(),v=read();

            cut(x,y);link(u,v);

        }

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

            int z=read();

            find(x,y);modify_b(y,z);

        }

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

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

        }

    }

    return ;

}