vector<int>e[N];
int w[N], dfn[N], subsize[N], fa[N], dep[N], wson[N], top[N];
int tol;
int v[N];
int R[N];
void dfs1(int x, int f) {
    subsize[x] = 1;
    fa[x] = f;
    for (int i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (y == f)continue;
        dep[y] = dep[x] + 1;
        dfs1(y, x);
        subsize[x] += subsize[y];
        if (subsize[y] > subsize[wson[x]])wson[x] = y;
    }
}



void dfs2(int x, int t) {
    dfn[x] = ++tol;
    w[tol] = v[x];
    top[x] = t;
    if (wson[x])dfs2(wson[x], t);
    for (int i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (y == fa[x] || y == wson[x])continue;
        dfs2(y, y);
    }
    R[x] = tol;
}


struct node {
    ll v, lz;
    int l, r;
}t[N * 4];

void pushup(int p) {
    t[p].v = t[p * 2].v + t[p * 2 + 1].v;
}

void pushdown(int p) {
    if (t[p].lz) {
        t[p * 2].v += t[p].lz*(t[p * 2].r - t[p * 2].l + 1);
        t[p * 2].lz += t[p].lz;
        t[p * 2 + 1].v += t[p].lz*(t[p * 2 + 1].r - t[p * 2 + 1].l + 1);
        t[p * 2 + 1].lz += t[p].lz;
        t[p].lz = 0;
    }
}

void build(int l, int r, int p) {
    t[p].l = l;
    t[p].r = r;
    t[p].v = 0;
    t[p].lz = 0;
    if (l == r) {
        t[p].v = w[l];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, p * 2);
    build(mid + 1, r, p * 2 + 1);
    pushup(p);
}


void update(int L, int R, int v, int p) {
    int l = t[p].l, r = t[p].r;
    if (L <= l && r <= R) {
        t[p].v += v * (r - l + 1);
        t[p].lz += v;
        return;
    }
    int mid = l + r >> 1;
    pushdown(p);
    if (mid >= L)update(L, R, v, p * 2);
    if (mid < R)update(L, R, v, p * 2 + 1);
    pushup(p);
}

ll query(int L, int R, int p) {
    int l = t[p].l, r = t[p].r;
    if (L <= l && r <= R) {
        return t[p].v;
    }
    int mid = l + r >> 1;
    pushdown(p);
    ll sum = 0;
    if (mid >= L)sum = (sum + query(L, R, p * 2)) % mod;
    if (mid < R)sum = (sum + query(L, R, p * 2 + 1)) % mod;
    return sum;
}

struct seg {
    int l, r;
}s[N];
int split(int x, int y) {
    int cnt = 0;
    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] < dep[fy]) {
            swap(fx, fy);
            swap(x, y);
        }
        s[cnt].l = dfn[fx];
        s[cnt++].r = dfn[x];
        x = fa[fx];
        fx = top[x];
    }
    if (dfn[x] > dfn[y])swap(x, y);
    s[cnt].l = dfn[x], s[cnt++].r = dfn[y];
    return cnt;
}


void init(int root, int n) {
    tol = 0;
    dfs1(root, 0);
    dfs2(root, root);
    build(1, n, 1);
}


void  path_update(int x, int y, int z) {
    int n = split(x, y);
    for (int i = 0; i < n; i++)
        update(s[i].l, s[i].r, z, 1);
}
ll path_query(int x, int y) {
    int n = split(x, y);
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans = (ans + query(s[i].l, s[i].r, 1)) % mod;
    return ans;
}

void subtree_update(int x, int z) {
    update(dfn[x], R[x], z, 1);
}

ll subtree_query(int x) {
    return query(dfn[x], R[x], 1);
}

int lca(int x, int y) {

    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] < dep[fy]) {
            swap(fx, fy);
            swap(x, y);
        }
        x = fa[fx];
        fx = top[x];
    }
    if (dep[x] > dep[y])
        return y;
    else
        return x;
}