Allen, Nella's older brother, has a better way of building graphs; he plugs them into his graph generator! The generator takes items as input:
- An initial graph
consisting of
nodes labeled from
to
connected by
distinct undirected edges of length
.
- An array
of length
, where
if nodes labeled
are producers and
otherwise.
- A positive integer
, the number of generation phases.
The generator then begins building the graph, happening in generation phases. In the first phase, the graph
is constructed. Then, for every phase after the first, the generator does the following:
For every node that is a producer constructed in the previous phase, construct a copy of
and connect node
of the copy to
with an undirected edge of length
.
To estimate the size of the graph constructed after the -th generation phase is over, compute the sum of the lengths of the shortest paths between every pair of nodes.
Constraints
is connected.
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
No additional constraints.
Input Specification
The first line contains integers
,
, and
.
The second line contains integers
.
The next lines each contain
integers
and
, the labels of the endpoints of the
-th edge in
. All edges are distinct, and there are no self-loops.
Output Specification
Output the sum of the lengths of the shortest paths between every pair of nodes. Since this value may be large, output it modulo .
Sample Input
2 1 2
1 1
1 2
Sample Output
35
Comments