High Fence Coloring#4565
There is a fence consisting of planks, lined up consecutively. Each plank must be painted entirely in one of the available colors. However, certain pairs of colors are incompatible, and it is not allowed for two adjacent planks to be painted in these colors. There are such incompatible pairs. Your task is to determine the number of valid ways to paint the fence, such that no two adjacent planks are painted in incompatible colors.
Constraints
, , and are integers. 1 \leq N \leq 10^{18}, 1 \leq C \leq 100, 0 \leq M \leq \dfrac{C(C+1)}{2}.
The first line contains three integers , , and .
Each of the next lines contains two integers, representing an incompatible pair of colors.
Print the remainder when the number of valid colorings of the fence is divided by 10^9 + 7.
Example 1