Simple Counting Problem, but Circular

問題文

円周上に $N$ 個の点が等間隔に並んでいます。 $K$ 種類の色があり、それぞれ色 $1, 2, \dots, K$ と呼びます。

$M$ 個の条件が与えられます。$i$ 番目の条件は組 $(x_i, y_i)$ で表され、 色 $x_i$ で塗られた点と色 $y_i$ で塗られた点が隣り合ってはならないことを示します。 $x_i = y_i$ の場合は、色 $x_i$ で塗られた点どうしが隣り合ってはならないことを示します。

これらの $N$ 個の点それぞれを $K$ 種類の色のいずれかで塗り、与えられた $M$ 個の条件をすべて満たす方法の個数を $1000000007$ で割った余りを出力してください。 ただし、回転によって一致するような塗り分けは1通りとして数えてください。

制約

• $3 \leq N \leq 10^{9}$
• $2 \leq K \leq 5$
• $1 \leq M \leq \frac{K (K + 1)}{2}$
• $1 \leq x_i \leq y_i \leq K \quad (1 \leq i \leq M)$
• $(x_i, y_i) \neq (x_j, y_j) \quad (1 \leq i \lt j \leq M)$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを $1$ 行で出力せよ。

サンプル 1

入力

3 3 1
1 2

出力

7

色 $1$ を黒、色 $2$ を白、色 $3$ を赤で表すと、以下の $7$ 通りが条件を満たします。

サンプル 2

入力

9 2 1
1 1

出力

10

色 $1$ を黒、色 $2$ を白で表すと、以下の $10$ 通りが条件を満たします。

サンプル 3

入力

1000000000 5 3
1 2
2 3
4 4

出力

142911141

答えを $1000000007$ で割った余りを出力してください。