Problem Description
Jie Feng the Physics Whiz has just invented some new magnets. These magnets are cubic in shape come in C different colours, numbered from 1 to C.
Two magnets can either attract or repel each other when they are placed next to each other. Jie Feng knows that there are R distinct ordered pairs of colours of magnets (Ai, Bi) that will repel each other. The two magnets will only repel each other when the magnet of colour Bi is placed after the magnet of colour Ai.
Jie Feng wants to construct a bar magnet of N of the new magnets. He can use any number of any type of magnets. However, he must ensure that no two adjacent magnets in the bar magnet repel each other.
Jie Feng wants you to help him calculate how many distinct bar magnets he can make. Help him calculate this number, modulo 109 + 7.
Input
The first line of input will contain three integers, N, C and R.
The next R lines of input will contain two integers each, Ai and Bi.
Output
Output a single integer, the number of distinct bar magnets, modulo 109 + 7.
Limits
For all subtasks, 1 ≤ Ai, Bi ≤ C. 0 ≤ R ≤ C2
Subtask 1 (23%): 1 ≤ N ≤ 1015. 1 ≤ C ≤ 52. R = 0.
Subtask 2 (19%): 1 ≤ N ≤ 8. 1 ≤ C ≤ 9.
Subtask 3 (25%): 1 ≤ N ≤ 15. 1 ≤ C ≤ 15.
Subtask 4 (33%): 1 ≤ N ≤ 1015. 1 ≤ C ≤ 52.
Subtask 5 (0%): Sample Testcases
Sample Testcase 1
Input
3 3 2
1 2
2 1
Output
17