#include using namespace std; using Int = long long; template struct LinkCutTree{ struct Node{ Node *l,*r,*p; size_t cnt; int idx; bool rev; T val,dat; E laz; Node():cnt(0){} Node(int idx,T val,E laz): cnt(1),idx(idx),rev(0),val(val),dat(val),laz(laz){l=r=p=nullptr;} bool is_root(){ return !p||(p->l!=this&&p->r!=this); } }; using F = function; using G = function; using H = function; using P = function; F f; G g; H h; P p; T ti; E ei; const size_t LIM = 1e6; vector pool; size_t ptr; LinkCutTree(F f,G g,H h,P p,T ti,E ei): f(f),g(g),h(h),p(p),ti(ti),ei(ei),pool(LIM),ptr(0){} inline Node* create(){ return &pool[ptr++]; } inline Node* create(int idx,T v){ return &(pool[ptr++]=Node(idx,v,ei)); } void propagate(Node *t,E v){ t->laz=h(t->laz,v); t->val=g(t->val,v); t->dat=g(t->dat,p(v,t->cnt)); } void toggle(Node *t){ swap(t->l,t->r); swap(t->dat.first,t->dat.second); t->rev^=1; } void eval(Node *t){ if(t->laz!=ei){ if(t->l) propagate(t->l,t->laz); if(t->r) propagate(t->r,t->laz); t->laz=ei; } if(t->rev){ if(t->l) toggle(t->l); if(t->r) toggle(t->r); t->rev=false; } } void update(Node *t){ t->cnt=1; t->dat=t->val; if(t->l) t->cnt+=t->l->cnt,t->dat=f(t->l->dat,t->dat); if(t->r) t->cnt+=t->r->cnt,t->dat=f(t->dat,t->r->dat); } void rotR(Node *t){ Node *x=t->p,*y=x->p; if((x->l=t->r)) t->r->p=x; t->r=x;x->p=t; update(x);update(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; update(y); } } void rotL(Node *t){ Node *x=t->p,*y=x->p; if((x->r=t->l)) t->l->p=x; t->l=x;x->p=t; update(x);update(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; update(y); } } void splay(Node *t){ eval(t); while(!t->is_root()){ Node *q=t->p; if(q->is_root()){ eval(q);eval(t); if(q->l==t) rotR(t); else rotL(t); }else{ auto *r=q->p; eval(r);eval(q);eval(t); if(r->l==q){ if(q->l==t) rotR(q),rotR(t); else rotL(t),rotR(t); }else{ if(q->r==t) rotL(q),rotL(t); else rotR(t),rotL(t); } } } } Node* expose(Node *t){ Node *rp=nullptr; for(Node *c=t;c;c=c->p){ splay(c); c->r=rp; update(c); rp=c; } splay(t); return rp; } void link(Node *par,Node *c){ expose(c); expose(par); c->p=par; par->r=c; } void cut(Node *c){ expose(c); Node *par=c->l; c->l=nullptr; par->p=nullptr; } void evert(Node *t){ expose(t); toggle(t); eval(t); } bool is_connected(Node *a,Node *b){ expose(a); while(a->l) a=a->l; expose(b); while(b->l) b=b->l; return a==b; } Node *lca(Node *a,Node *b){ expose(a); return expose(b); } void set_propagate(Node *t,E v){ expose(t); propagate(t,v); eval(t); } }; //INSERT ABOVE HERE struct M{ Int a,b,c,d; M():a(1),b(0),c(0),d(1){} M(Int a,Int b,Int c,Int d):a(a),b(b),c(c),d(d){} //M(const M &v):a(v.a),b(v.b),c(v.c),d(v.d){} bool operator!=(const M &x)const{ return a!=x.a||b!=x.b||c!=x.c||d!=x.d; } bool operator==(const M &x)const{ return !(*this!=x); } }E; signed main(){ const int MOD=1e9+7; using M2 = pair; using LCT = LinkCutTree; auto f=[MOD](M x,M y){ M r(0,0,0,0); r.a=x.a*y.a+x.b*y.c; r.b=x.a*y.b+x.b*y.d; r.c=x.c*y.a+x.d*y.c; r.d=x.c*y.b+x.d*y.d; r.a%=MOD;r.b%=MOD;r.c%=MOD;r.d%=MOD; return r; }; auto f2=[&](M2 x,M2 y){ return M2(f(x.first,y.first),f(y.second,x.first)); }; auto g=[](M2 x,M2 y){x.first.a++;return y;}; auto p=[](M2 x,size_t y){y++;return x;}; int n; cin>>n; vector > G(n); vector X,Y; for(int i=1;i>a>>b; X.emplace_back(a); Y.emplace_back(b); G[a].emplace_back(b); G[b].emplace_back(a); } M ti=M(); M ei(-1,-1,-1,-1); LCT lct(f2,g,g,p,M2(ti,ti),M2(ei,ei)); vector vs(n*2-1); for(int i=0;i<(int)vs.size();i++) vs[i]=lct.create(i,M2(ti,ti)); vector > rev(n); int idx=n; { using P = pair; queue

q; q.emplace(0,-1); while(!q.empty()){ int v,p; tie(v,p)=q.front();q.pop(); if(~p){ lct.link(vs[p],vs[idx]); lct.link(vs[idx],vs[v]); rev[p][v]=rev[v][p]=idx++; } for(int u:G[v]) if(u!=p) q.emplace(u,v); } } int q; cin>>q; for(int i=0;i>c; if(c=='x'){ Int v,a,b,c,d; cin>>v>>a>>b>>c>>d; int z=rev[X[v]][Y[v]]; lct.expose(vs[z]); vs[z]->val=M2(M(a,b,c,d),M(a,b,c,d)); lct.expose(vs[z]); } if(c=='g'){ Int x,y; cin>>x>>y; lct.evert(vs[x]); lct.expose(vs[y]); M ans=vs[y]->dat.first; cout<