Song Composition Under Constraints

IA is a singing girl who is preparing a song for IOI2018. The song consists of \(n\) musical notes with pitches \(h_1, h_2, \ldots, h_n\). Her vocal range is \(A\), meaning she can only sing integer pitches in the range \(1\) to \(A\) (i.e. \(1 \le h_i \le A\)).

Before composing the song, IA writes down \(Q\) restrictions to define its structure. The \(i\)-th restriction is described by three integers \(l_i\), \(r_i\) and \(m_i\), meaning that the maximum pitch among the notes \(h_{l_i}, h_{l_i+1}, \ldots, h_{r_i}\) must be exactly \(m_i\) (i.e. \(\max\{h_{l_i}, h_{l_i+1}, \ldots, h_{r_i}\} = m_i\)).

Your task is to determine the number of possible songs (i.e. sequences \(h_1, h_2, \ldots, h_n\)) that satisfy all the restrictions. Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains three integers \(n\), \(A\) and \(Q\).

Each of the next \(Q\) lines contains three integers \(l_i\), \(r_i\) and \(m_i\) representing a restriction.

It is guaranteed that \(1 \le l_i \le r_i \le n\) and \(1 \le m_i \le A\).

outputFormat

Output a single integer: the number of valid songs modulo \(10^9+7\).

sample

3 5 2
1 3 3
2 2 2

5