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 $A_i + A_j = 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 \le n, m, q \le 7$.
- $1 \le i, j \le n$.
- $1 \le k \le 14$.
### Example
Input:
```
2 2 1
1 2 3
```
Output:
```
2
```
