//It is made by Awson on 2018.1.16

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Abs(a) ((a) < 0 ? (-(a)) : (a))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 using namespace std;

 const int MOD = ;

 const int N = 1e5;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(int x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 char ch[];

 int n, q, u, v, c;

 struct Link_Cut_Tree {

     int ch[N+][], pre[N+], rev[N+], sum[N+], prod[N+], val[N+], tol[N+], isrt[N+], size[N+];

     Link_Cut_Tree() {for (int i = ; i <= N; i++) val[i] = tol[i] = isrt[i] = prod[i] = size[i] = ; }

     void pushup(int o) {tol[o] = (tol[ch[o][]]+tol[ch[o][]]+val[o])%MOD, size[o] = (size[ch[o][]]+size[ch[o][]]+)%MOD; }

     void pushdown(int o) {

     int ls = ch[o][], rs = ch[o][];

     if (rev[o]) {

         Swap(ch[ls][], ch[ls][]), Swap(ch[rs][], ch[rs][]);

         rev[ls] ^= , rev[rs] ^= , rev[o] = ;

     }

     if (prod[o] != ) {

         prod[ls] = (LL)prod[ls]*prod[o]%MOD, prod[rs] = (LL)prod[rs]*prod[o]%MOD;

         sum[ls] = (LL)sum[ls]*prod[o]%MOD, sum[rs] = (LL)sum[rs]*prod[o]%MOD;

         val[ls] = (LL)val[ls]*prod[o]%MOD, val[rs] = (LL)val[rs]*prod[o]%MOD;

         tol[ls] = (LL)tol[ls]*prod[o]%MOD, tol[rs] = (LL)tol[rs]*prod[o]%MOD;

         prod[o] = ;

     }

     if (sum[o]) {

         sum[ls] = (sum[ls]+sum[o])%MOD, sum[rs] = (sum[rs]+sum[o])%MOD;

         val[ls] = (val[ls]+sum[o])%MOD, val[rs] = (val[rs]+sum[o])%MOD;

         tol[ls] = (tol[ls]+(LL)sum[o]*size[ls]%MOD)%MOD, tol[rs] = (tol[rs]+(LL)sum[o]*size[rs]%MOD)%MOD;

         sum[o] = ;

     }

     }

     void push(int o) {

     if (!isrt[o]) push(pre[o]);

     pushdown(o);

     }

     void rotate(int o, int kind) {

     int p = pre[o];

     ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p;

     if (isrt[p]) isrt[o] = , isrt[p] = ;

     else ch[pre[p]][ch[pre[p]][] == p] = o;

     pre[o] = pre[p];

     ch[o][kind] = p, pre[p] = o;

     pushup(p), pushup(o);

     }

     void splay(int o) {

     push(o);

     while (!isrt[o]) {

         if (isrt[pre[o]]) rotate(o, ch[pre[o]][] == o);

         else {

         int p = pre[o], kind = ch[pre[p]][] == p;

         if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind);

         else rotate(p, kind), rotate(o, kind);

         }

     }

     }

     void access(int o) {

     int y = ;

     while (o) {

         splay(o);

         isrt[ch[o][]] = , isrt[ch[o][] = y] = ;

         pushup(o); o = pre[y = o];

     }

     }

     void makeroot(int o) {access(o), splay(o); rev[o] ^= , Swap(ch[o][], ch[o][]); }

     void link(int x, int y) {makeroot(x); pre[x] = y; }

     void cut(int x, int y) {makeroot(x), access(y), splay(y); ch[y][] = pre[x] = , isrt[x] = ; pushup(y); }

     void split(int x, int y) {makeroot(x), access(y), splay(y); }

     void add(int x, int y, int c) {split(x, y); sum[y] = (sum[y]+c)%MOD, val[y] = (val[y]+c)%MOD, tol[y] = (tol[y]+(LL)c*size[y]%MOD)%MOD; }

     void plus(int x, int y, int c) {split(x, y); prod[y] = (LL)prod[y]*c%MOD, sum[y] = (LL)sum[y]*c%MOD, val[y] = (LL)val[y]*c%MOD, tol[y] = (LL)tol[y]*c%MOD; }

     int query(int x, int y) {split(x, y); return tol[y]; }

 }T;

 void work() {

     read(n), read(q);

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

     read(u), read(v); T.link(u, v);

     }

     while (q--) {

     scanf("%s", ch);

     if (ch[] == '+') {read(u), read(v), read(c); T.add(u, v, c); }

     else if (ch[] == '-') {

         read(u), read(v); T.cut(u, v);

         read(u), read(v); T.link(u, v);

     }

     else if (ch[] == '*') {read(u), read(v), read(c); T.plus(u, v, c); }

     else if (ch[] == '/') {read(u), read(v); write(T.query(u, v)), putchar('\n'); }

     }

 }

 int main() {

     work();

     return ;

 }