Vanya loves all numbers divisible by the number M. Now, given 2 numbers N and M, she gives you the following task : Given 2 numbers N and M, you need to count the number of numbers consisting of N digits that have value greater than 0 and are divisible by M. All numbers should be valid numbers, and should not contain any leading zeros.

In retrospect, Vanya realized that this task might be just too easy for you, and adds the following constraint : She gives you X pairs of numbers, each pair consists of 2 numbers from 1 to 9. Given these pairs , assume one of them to be consisting of numbers a and b, you need to eliminate out all numbers in which a and b appear adjacent to each other.They should not be adjacent in any order, i.e \(a,b\) (in that order) as well as \(b,a\) (in that order) are not valid. After this elmination process, you need to report the number of valid numbers.

As the answer could be rather large, print it Modulo \(10^9+7\).

Input Format :

The first line of the input consists of a single integer T, denoting the number of test cases. The description of each test case is spread out as follows :

The first line of each test case consists of 3 integers N, M and X. Each of the next X lines contains 2 integers a and b, denoting the numbers a and b should not appear adjacent to each other in any of the valid numbers. It is guaranteed that there shall be no 2 pairs, where \(a_{i} = a_{j} \) and \(b_{i} = b_{j} \).

Output Format :

For each test case, print the answer on a new line. As the answer can be rather large, print it Modulo \(10^9+7\).

Constraints :

\( 1 \le T \le 10 \)

\( 1 \le N \le 10^3 \)

\( 1 \le M \le 100 \)

\( 1 \le X \le 81 \)

\( 1 \le a_{i} , b_{i} \le 9 \)