D. Beautiful Dices
time limit per test
7 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing a game of "chaos dice". According to the rules of the game, players take turns rolling $$$k$$$-sided dice and write down the sequence of numbers $$$a_i$$$ that appear on them (numbered from $$$1$$$) until the sequence becomes of length $$$n$$$ ($$$n$$$ is odd).

Lets denote the central index of the sequence as $$$c$$$, i.e., $$$c = \frac{n+1}{2}$$$. You win only if the sequence satisfies the following three criteria:

  1. the number $$$k$$$ appears only once and is exactly in the middle of the sequence; more formally — $$$a_c = k$$$ and $$$a_i \ne k$$$ for all $$$i \ne c$$$;
  2. the numbers on one side of the center at distances differing by a factor of two are the same; that is, for any $$$d$$$ from $$$-\left\lfloor\frac{c-1}{2}\right\rfloor$$$ to $$$-1$$$ and from $$$1$$$ to $$$\left\lfloor\frac{c-1}{2}\right\rfloor$$$, $$$a_{c+d} = a_{c+2d}$$$;
  3. each of game master's $$$m$$$ favorite number pairs $$$(x_i, y_i)$$$ appears in the sequence as consecutive values no more than once.

In any other case, game master wins. It is worth noting that game master's favorite number pairs are ordered, so if game master likes the number pair $$$(x_i, y_i)$$$, it is not guaranteed that he likes a pair $$$(y_i, x_i)$$$.

Your task is to calculate the total number of sequences of numbers from $$$1$$$ to $$$k$$$ of length $$$n$$$ that satisfy the described conditions. Calculate this number modulo $$$10^9 + 7$$$, as it may be too large.

Input

The first line of input contains three integers $$$n$$$, $$$k$$$, and $$$m$$$ — the required number of dice rolls (length of the sequence), the number of sides on the die, and the number of game master's favorite number pairs ($$$1 \le n \le 53$$$; $$$n$$$ is odd; $$$2 \le k \le 10$$$; $$$0 \le m \le 16$$$). It is guaranteed that $$$(k - 1)^{n-1} \le 10^{36}$$$.

In the $$$i$$$-th of the following $$$m$$$ lines, a pair of numbers $$$x_i$$$ and $$$y_i$$$ is given — the $$$i$$$-th of game masters's favorite number pairs ($$$1 \le x_i, y_i \le k$$$). It is guaranteed that all pairs are distinct.

Output

Output a single integer — the number of sequences of length $$$n$$$ that satisfy all the conditions.

Examples
Input
3 6 1
6 6
Output
25
Input
5 8 1
1 2
Output
49
Input
7 5 2
1 2
2 1
Output
254