Counting Colored Trees with Colorful Paths

Vito and Karlo are fascinated by the colorful trees. Each tree can be seen as a tree graph – an undirected connected acyclic graph – where every edge is colored with one of \(k\) colors. A path is called colorful if it contains at least two different colors. This property is non‐trivial since a path formed by a single edge (or having all edges of the same color) is not considered colorful.

This problem gives you an integer \(n\) representing the number of nodes, an integer \(k\) for the number of available colors, and an integer \(m\) denoting the number of queries. Although the tree structure is not provided, you are told that the trees under consideration are all possible labeled trees on \(n\) nodes. In addition, for each of the \(m\) queries you are given two endpoints \(u\) and \(v\) (using 1–indexing), and you must ensure that in the chosen tree the unique path from \(u\) to \(v\) is colorful. In other words, when traversing the unique path between \(u\) and \(v\), the colors of the edges on that path must not all be identical.

Your task is to count the number of pairs (tree structure, valid edge coloring) among all labeled trees on \(n\) nodes where every edge is colored with one of \(k\) colors and for each given query the corresponding path is colorful. Output your answer modulo \(10^9+7\).

Note: Since any path consisting of a single edge cannot be colorful (it only contains one color), if a query corresponds to an edge in the tree then that tree is automatically invalid.

inputFormat

The first line of input contains three integers \(n\), \(k\), and \(m\): the number of nodes, the number of colors, and the number of queries, respectively.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) (1–indexed) that denote the endpoints of a query. For each query, the unique path between \(u\) and \(v\) in the tree must be colorful.

outputFormat

Output a single integer – the number of valid pairs (tree, colored assignment) modulo \(10^9+7\).

sample

2 3 1
1 2

0