#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 (*A _{i}*,

*B*) that will repel each other. The two magnets will only repel each other when the magnet of colour

_{i}*B*is placed after the magnet of colour

_{i}*A*.

_{i}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 10^{9} + 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, *A _{i}* and

*B*.

_{i}## Output

Output a single integer, the number of distinct bar magnets, modulo 10^{9} + 7.

## Limits

For all subtasks, 1 ≤ *A _{i}*,

*B*≤

_{i}*C*. 0 ≤

*R*≤

*C*

^{2}

Subtask 1 (23%): 1 ≤ *N* ≤ 10^{15}. 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* ≤ 10^{15}. 1 ≤ *C* ≤ 52.

Subtask 5 (0%): Sample Testcases

## Sample Testcase 1

### Input

3 3 2 1 2 2 1

### Output

17

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 23 | 20 | 1s | 64MB | Minimum |

2 | 19 | 30 | 1s | 64MB | Minimum |

3 | 25 | 30 | 1s | 64MB | Minimum |

4 | 33 | 30 | 1s | 64MB | Minimum |

5 | 0 | 1 | 1s | 64MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o magnets -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512