#include <cstdio>

#include <algorithm>

#define l(x) t[x].s[0]

#define r(x) t[x].s[1]

#define f(x) t[x].f

#define lc(x) (r(f(x)) == x)

#define int unsigned int

const int N = , p = ;

char op[];

int n,m,x,y,c,tp,q[N];

struct nd {int v,f,s[],sm,sz,mu,ad,rv;}t[N];

bool rt(int x) {return l(f(x)) != x && r(f(x)) != x;}

void cal(int x, int m, int a) {

    if(!x) return;

    t[x].v = (t[x].v*m+a)%p, t[x].sm = (t[x].sm*m+a*t[x].sz)%p, t[x].mu = t[x].mu*m%p, t[x].ad = (t[x].ad*m+a)%p;

}

void pu(int x) {t[x].sm = (t[l(x)].sm+t[r(x)].sm+t[x].v)%p, t[x].sz = (t[l(x)].sz+t[r(x)].sz+)%p;}

void pd(int x) {

    if(t[x].rv) t[x].rv = , t[l(x)].rv ^= , t[r(x)].rv ^= , std::swap(l(x),r(x));

    if(t[x].mu !=  || t[x].ad) cal(l(x),t[x].mu,t[x].ad),cal(r(x),t[x].mu,t[x].ad);

    t[x].mu = , t[x].ad = ;

}

void rot(int x) {

    int y = f(x), z = f(y), xx = r(y)==x;

    if(!rt(y)) t[z].s[r(z)==y] = x;

    f(x) = z, f(y) = x, f(t[x].s[!xx]) = y;

    t[y].s[xx] = t[x].s[!xx], t[x].s[!xx] = y;

    pu(y);

}

void sp(int x) {

    q[++tp] = x;

    for(int i = x; !rt(i); i = f(i)) q[++tp] = f(i);

    while(tp) pd(q[tp--]);

    for(int y = f(x); !rt(x); rot(x),y=f(x)) if(!rt(y)) {

        if(lc(x)^lc(y)) rot(x); else rot(y);

    }

    pu(x);

}

void acs(int x) {for(int y = ; x; x = f(x)) sp(x), r(x) = y, pu(y=x);}

void mkrt(int x) {acs(x), sp(x), t[x].rv ^= ;}

void spli(int x, int y) {mkrt(y), acs(x), sp(x);}

void lk(int x, int y) {mkrt(x), f(x) = y;}

void cut(int x, int y) {mkrt(x), acs(y), sp(y), l(y) = f(x) = , pu(y);}

signed main() {

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

    for(int i = ; i <= n; i++) t[i].v = t[i].sm = t[i].sz = t[i].mu = ;

    for(int i = ; i < n; i++) scanf("%d%d", &x, &y), lk(x,y);

    while(m--) {

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

        if(op[] == '+') scanf("%d", &c), spli(x,y), cal(x,,c);

        else if(op[] == '-') cut(x,y), scanf("%d%d", &x, &y), lk(x,y);

        else if(op[] == '*') scanf("%d", &c), spli(x,y), cal(x,c,);

        else spli(x,y), printf("%d\n", t[x].sm);

    }

    return ;

}