Description

在梦里，小 C 进入了一个 $n$ 个点 $m$ 条边的有向迷宫，第 $i$ 条边从 $u_i$ 通向 $v_i$。小 C 会从某个点出发，每次随机选择一条出边走过去，一条边被选中的概率与它的权重 $w_i$ 成正比。也就是说，若小 C 在 $i$ 号点，设 $i$ 号点出边的权重之和为 $\sum w_i$，则他选择一条出边 $j$ 的概率为 $\frac{w_j}{\sum w_i}$。特别的，$n$ 号点是迷宫的出口，小 C 走到 $n$ 号点之后就会停止。

小 C 的梦境在不断地变化着，对于每条边还会给出三个参数 $s_i, c_i, p_i$，在 $t$ 时刻这条边的长度为 $s_i \times |t - p_i| + c_i$。

作为梦的创造者，小 C 走过迷宫的任意一条边都不需要耗费时间，也就是说从起点出发直至到达出口都处在同一时刻，但他希望知道经过的边的期望总长度是多少。他会给出 $q$ 个询问，每次给出 $t_i, x_i$，表示询问在 $t_i$ 时刻从 $x_i$ 开始走到出口所经过的期望路径长度，对 $10^9+7$ 取模。

具体来说，若答案化为最简分数的形式是 $\frac{x}{y}$，你需要输出 $x \times y^{-1}\bmod (10^9+7)$，其中 $y^{-1}$ 表示 $y$ 在模 $10^9+7$ 意义下的逆元。

Input

第一行三个整数 $n, m, q$ ($2 \le n \le 400, 1 \le m \le \min\{10^5, n(n - 1)\}, 1 \le q \le 2 \times 10^6$)。

接下来 $m$ 行，每行六个整数 $u_i, v_i, w_i, s_i, c_i, p_i$ ($1 \le u_i,v_i \le n,u_i \neq v_i,1 \le w_i \le 10^3,1 \le s_i, c_i \le 10^9,$ $0\le p_i\le 10^9$)，描述一条边。保证从每个点出发都能到达 $n$ 号点，图中没有重边（$(u, v)$ 和 $(v, u)$ 不视为重边）。

接下来 $q$ 行，每行两个整数 $t_i, x_i$ ($0\le t_i\le 10^9,1\le x_i\le n$)，描述一次询问。

Output

输出 $q$ 行，每行一个整数表示询问的答案。

Samples

2 2 2
1 2 9 2 3 3
2 1 3 3 3 4
7 1
2 1

11
5

4 4 6
1 2 3 4 5 6
2 3 3 1 2 2
3 4 7 1 1 9
3 1 8 2 10 12
1 1
3 2
7 3
10 2
15 1
100 4

571428681
857142928
142857188
428571495
285714433
0

Resources

The 22nd UESTC Programming Contest Preliminary