A k-path on a given undirected graph is a path having exactly k edges and containing no repeated nodes. Given an undirected graph G and an integral value k, count how many k-paths on G. There six 3-paths on the graph in Figure 1 which are: 1-2-3-4, 2-3-4-1, 3-4-1-2, 4-1-2-3, 2-1-3-4, 4-1-3-2

Input

The input consists of following lines

? Line 1: contains two integer n and k (1 = < n = < 30, 1 = < k = < 10) in which n is the number of nodes of the graph G (nodes are numbered 1,2,...,n)

? Line 2: contains an integer m (1 = < m = < 60) which is the number of edges of G

? Line i + 2: contains two integers u and v representing two end points of the ith edge of G (8i = 1;......m)

Output

The output contains the number of k-paths of G

Example

Input

4 3

5

1 2

1 3

1 4

2 3

3 4

Output

6