Valid Training Plans under Bitwise Conditions

In this problem, you are given three integers \(n\), \(k\) and \(m\). A training plan is an array \(a = [a_1, a_2, \dots, a_n]\) where every \(a_i\) is an integer satisfying \(0 \le a_i \le k\). The plan is valid if it satisfies the following two properties:

1. Chain condition: For every \(1 \le i < j \le n\) it holds that \[ a_i \mathbin{\&} a_j = a_i, \] where \(\&\) denotes the bitwise AND operator. Equivalently, the binary representation of \(a_i\) is a subset of that of \(a_j\); note that equality is allowed.
2. Binary restrictions: There are \(m\) restrictions. Each restriction is given by two indices \(l_i\) and \(r_i\) (with \(1 \le l_i < r_i \le n\)), and requires that \(a_{l_i} \neq a_{r_i}\). This is imposed to avoid stagnation by forbidding the use of the same training set in the specified iterations.

Your task is to count the number of valid training plans modulo \(10^9+7\).

Explanation: The chain condition forces the sequence to be "bitwise non‐decreasing" – once a bit is turned on it remains on. In other words, for every bit position the sequence of bits is a series of 0's followed by 1's. However, different bits may turn on at different iterations subject to \(0 \le a_i \le k\), so not every subset of bits is allowed. Furthermore, the \(m\) binary restrictions force that, for some pairs of iterations, the plan must actually have a change (i.e. the two corresponding values must be different).

inputFormat

The first line contains three integers \(n\), \(k\) and \(m\) \( (1 \le n \le \text{small},\; 0 \le k \le \text{small},\; 0 \le m \le 10)\).

Each of the next \(m\) lines contains two integers \(l_i\) and \(r_i\) (\(1 \le l_i < r_i \le n\)) representing a binary restriction that forces \(a_{l_i} \neq a_{r_i}\).

outputFormat

Output a single integer — the number of valid training plans modulo \(10^9+7\).

sample

3 5 1
1 3

22