Tree Transport Cost

You are given a tree with n nodes. Each edge has two weights: \(D_i\) and \(T_i\). You are also given a constant parameter \(G\). There are \(Q\) operations, each of which is one of the following two types:

• 0 x y t: Update the \(T\) value on the edge connecting nodes \(x\) and \(y\) to t.
• 1 x y: Query the transport cost from node \(x\) to node \(y\).

The transport process is defined as follows. Suppose we want to transport some initial value \(X\) from \(x\) to \(y\) along the unique simple path consisting of edges \(e_1, e_2, \ldots, e_k\). When traversing an edge \(e_i\) with weights \(D_i\) and \(T_i\), the current transported value is first decreased by \(T_i\), and then a cost equal to \(D_i\) times the current value (after the decrease) is incurred. In order for the value arriving at \(y\) to be exactly \(G\), the initial value must satisfy:

\[ X - \sum_{i=1}^{k} T_i = G \quad \Longrightarrow \quad X = G + \sum_{i=1}^{k} T_i. \]

Therefore, the total cost incurred along the path is computed as follows. Let the edges along the path be processed in order; then the cost is given by:

\[ \text{Cost} = \sum_{i=1}^{k} D_i \Bigl(G + \sum_{j=i}^{k} T_{j}\Bigr) = \Bigl(G + \sum_{i=1}^{k} T_i\Bigr) \Bigl(\sum_{i=1}^{k} D_i\Bigr) - \sum_{i=1}^{k} D_i \Bigl(\sum_{j=1}^{i-1} T_j\Bigr). \]

Since the cost can be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains three integers \(n\), \(Q\), and \(G\) — the number of nodes in the tree, the number of operations, and the target value at the destination, respectively.

Then, \(n-1\) lines follow. Each line contains four integers \(u\), \(v\), \(D\), and \(T\), representing an edge between nodes \(u\) and \(v\) with weights \(D\) and \(T\).

Then \(Q\) lines follow. Each line represents an operation in one of the following formats:

• 0 x y t
• 1 x y

outputFormat

For each operation of type 1 x y, output a single line containing the transport cost from node \(x\) to node \(y\) modulo \(10^9+7\).

sample

5 6 10
1 2 1 2
2 3 2 3
2 4 3 4
1 5 4 5
1 3 4
0 2 4 2
1 3 4
1 1 5
0 1 2 1
1 1 3

76
66
60
40

</p>