407017: GYM102687 D Kapuluan ng Kalayaan 2

Since the citizens of the country were not fussing about worrying how not to get arrested during quarantine, or hosting birthday mañanitas for their beloved police chief, the Philippines was able to finally rightfully claim the Spratly Islands as part of their territory, and even establish a successful system of ferries connecting the islands together, with tours! Do you remember how fulfilling it was to meticulously and lovingly craft optimal solutions to these problems, after you were put in charge of the project?

Of course, ever since you handed over leadership of the ferry project to another administration, the new management proceeded to thoughtlessly add more ferry routes and ruin the system you developed. But hey, you don't care about that, right? It doesn't matter that all your hard work was ruined by a new team that doesn't care about the project nearly as much as you did. Nope!

To recap, there are $$$n$$$ islands labeled $$$1$$$ to $$$n$$$, and $$$m$$$ ferry services that allow travel between pairs of islands. The $$$i$$$th ferry service connects islands $$$u_i$$$ and $$$v_i$$$, and due to the event-that-shall-not-be-named, citizens are only permitted to use this ferry if they are at least $$$d_i$$$ seconds old (because everyone knows their age down to the second, obviously). A ferry always connects two different islands, but the same pair of islands may have multiple ferry services between them.

Even though the ferry services are up and running again, people are generally discouraged from leaving their houses and returning to their home province (again, due to the event-that-shall-not-be-named). Despite this, some people still insist on leaving their islands anyway! You are aware of $$$k$$$ different rebellious souls, as well as each of their respective romantic partners (there are $$$k$$$ romantic partners in total). You also know the ages of the rebels—the $$$i$$$th rebel is $$$H_i$$$ seconds old.

How do we prevent them from visiting their romantic partners? Your master plan is simple!

You will build $$$2k$$$ houses on the islands, and relocate each of the rebels or romantic partners to these houses (one to each house), such that it is impossible for each rebel to ever reach the island of their partner by using the ferry system. The romantic partners can be assumed to stay in their assigned island and will never attempt to move. It is okay for multiple rebels or multiple partners to live on the same island, and it is even okay for a rebel to live on the same island as the partner of a different rebel, so long as it is impossible for them to reach their own partner.

How many ways can you choose where to build each of the $$$2k$$$ houses such that this condition is fulfilled? Two ways are different if one of the rebels or one of the partners has their home on a different island between the two ways. Since this can be quite large, output your answer modulo $$$10^9+7$$$.

The first line of input contains three space-separated integers, $$$n$$$, $$$m$$$, and $$$k$$$, respectively.

This is followed by $$$m$$$ lines, each containing three space-separated integers $$$u_i$$$, $$$v_i$$$, and $$$d_i$$$, meaning that there exists a ferry service connecting islands $$$u_i$$$ and $$$v_i$$$ that you have to be $$$d_i$$$ seconds old in order to use.

Finally, this is followed by a single line containing $$$k$$$ space-separated integers, where the $$$i$$$th of these integers is $$$H_i$$$.

Output a single line containing the answer modulo $$$10^9+7$$$.

For all subtasks

$$$2 \leq n \leq 10^6$$$

$$$1 \leq m, k \leq 2\cdot 10^5$$$

$$$1 \leq u_i, v_i \leq n$$$

$$$u_i \neq v_i$$$

$$$1 \leq d_i, H_i \leq 2\cdot10^9$$$

Subtask 1 (10 points):

$$$n, m, k \leq 20$$$

Subtask 2 (20 points):

$$$n, m, k \leq 200$$$

Subtask 3 (10 points):

$$$k = 1$$$

$$$n \leq 7641$$$

Subtask 4 (15 points):

$$$k = 1$$$

Subtask 5 (5 points):

$$$d_i$$$ is the same across all ferry services.

$$$n \leq 7641$$$

Subtask 6 (10 points):

$$$d_i$$$ is the same across all ferry services.

Subtask 7 (30 points):

No further constraints.

4 3 2
1 2 567600000
2 3 662300000
3 4 567600000
536100000 630700000

96

3 4 2
1 2 599200000
2 3 599200000
3 1 599200000
1 3 410000000
504600000 1009200000

0

7641 9 9
1 1521 6
1521 1896 9
1896 1916 12
1916 1942 15
1942 1945 18
1945 1965 21
1965 1986 24
1986 2016 27
2016 2020 30
12 1 2 1 14 12 5 14 9

110345126