Junior Fence Painting#4566
There is a fence made up of boards lined up in sequence. Each board needs to be painted entirely in one of the available colors. However, some color pairs are incompatible, meaning two adjacent boards cannot be painted in these colors. There are such incompatible pairs. Your task is to calculate the number of valid ways to paint the fence, ensuring no two adjacent boards are painted in incompatible colors.
Constraints
, , are integers. 1 \leq N \leq 10000, 1 \leq C \leq 100, 0 \leq M \leq \frac{C(C+1)}{2}.
The first line contains three integers: , , . Each of the next lines contains two integers, representing a pair of incompatible colors.
Print the remainder when the number of valid colorings of the fence is divided by 10^9 + 7.
Example 1