# #2340. 「WC2018」州区划分

#### 题目描述

$\left( \frac {\sum_{x \in V_i} w_x} {\sum_{j=1}^i \sum_{x \in V_j} w_x} \right)^p$

#### 样例 1 输入

3 2 1
1 2
2 3
1 1 1

#### 样例 1 输出

1

#### 提示

$x^{p-1} \equiv 1 \pmod p$，其中 $p$ 为质数，$x \in \left[1, p\right)$

#### 子任务

1 $10$ $5$ $2$
2 $10$ $10$ $2$
3 $10$ $15$ $0$
4 $10$ $15$ $1$
5 $10$ $15$ $2$
6 ~ 9 $5$ $21$ $0$
10 ~ 13 $5$ $21$ $1$
14 ~ 15 $5$ $21$ $2$