#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rd read()

 #define ll long long

 using namespace std;

 const int N = 1e5 + ;

 const int mod = ;

 int n, m;

 int read() {

     int X = , p = ; char c = getchar();

     for (; c > '' || c < ''; c = getchar())

         if (c == '-') p = -;

     for (; c >= '' && c <= ''; c = getchar())

         X = X *  + c - '';

     return X * p;

 }

 namespace LCT {

     int ch[N][], tun[N], f[N], size[N];

     ll sum[N], val[N], tim[N], ad[N];

 #define lc(x) ch[x][0]

 #define rc(x) ch[x][1]

     int isroot(int x) {

         return lc(f[x]) != x && rc(f[x]) != x;

     }

     int get(int x) {

         return rc(f[x]) == x;

     }

     void up(int x) {

         sum[x] = val[x];

         size[x] = ;

         if (lc(x)) sum[x] += sum[lc(x)], size[x] += size[lc(x)];

         if (rc(x)) sum[x] += sum[rc(x)], size[x] += size[rc(x)];

         sum[x] %= mod;

     }

     void time(int x, ll d) {

         val[x] = val[x] * d % mod;

         sum[x] = sum[x] * d % mod;

         ad[x] = ad[x] * d % mod;

         tim[x] = tim[x] * d % mod;

     }

     void add(int x, ll d) {

         sum[x] = (sum[x] + d * size[x]) % mod;

         val[x] = (val[x] + d) % mod;

         ad[x] = (ad[x] + d) % mod;

     }

     void rev(int x) {

         swap(lc(x), rc(x));

         tun[x] ^= ;

     }

     void pushdown(int x) {

         if (tim[x] != ) {

             if (lc(x)) time(lc(x), tim[x]);

             if (rc(x)) time(rc(x), tim[x]);

             tim[x] = ;

         }

         if (ad[x]) {

             if (lc(x)) add(lc(x), ad[x]);

             if (rc(x)) add(rc(x), ad[x]);

             ad[x] = ;

         }

         if (tun[x]) {

             if (lc(x)) rev(lc(x));

             if (rc(x)) rev(rc(x));

             tun[x] = ;

         }

     }

     void pd(int x) {

         if (!isroot(x))

             pd(f[x]);

         pushdown(x);

     }

     void rotate(int x) {

         int old = f[x], oldf = f[old], son = ch[x][get(x) ^ ];

         if (!isroot(old)) ch[oldf][get(old)] = x;

         ch[x][get(x) ^ ] = old;

         ch[old][get(x)] = son;

         f[old] = x; f[x] = oldf; f[son] = old;

         up(old); up(x);

     }

     void splay(int x) {

         pd(x);

         for (; !isroot(x); rotate(x))

             if(!isroot(f[x]))

                 rotate(get(f[x]) == get(x) ? f[x] : x);

     }

     void access(int x) {

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

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

     }

     void mroot(int x) {

         access(x); splay(x); rev(x);

     }

     void split(int x, int y) {

         mroot(x); access(y); splay(y);

     }

     void link(int x, int y) {

         mroot(x);

         f[x] = y;

     }

     void cut(int x, int y) {

         split(x, y);

         f[x] = ch[y][] = ;

         up(y);

     }

 }

 using namespace LCT;

 int main()

 {

     n = rd; m = rd;

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

         size[i] = tim[i] = val[i] = sum[i] = ;

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

         int u = rd, v = rd;

         link(u, v);

     }

     for (; m; m--) {

         char op[];

         scanf("%s", op);

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

             int u = rd, v = rd, d = rd;

             split(u, v);

             add(v, d);

         }

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

             int u = rd, v = rd;

             cut(u, v);

             u = rd; v = rd;

             link(u, v);

         }

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

             int u = rd, v = rd, d = rd;

             split(u, v);

             time(v, d);

         }

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

             int u = rd, v = rd;

             split(u, v);

             printf("%lld\n", sum[v] % mod);

         }

     }

 }