Count the number of positive integer array A of length n that:
- Each element does not exceed m.
- Satisfy q conditions, each of the form (i,j,k) means that Ai+Aj=k.
### Input
- The first line contains 3 integers n,m,q.
- Each line in the next q lines contains 3 integers i,j,k.
### Output
- The number of arrays sastify the given conditions.
### Constraints
- 1≤n,m,q≤7.
- 1≤i,j≤n.
- 1≤k≤14.
### Example
Input:
221123
Output:
2
