Circle Seating Arrangement with Restrictions

There are \(n\) people (numbered from \(1\) to \(n\)) sitting around a circular table. The absolute difference between the numbers of any two adjacent persons must not exceed \(p\), i.e., for any two adjacent persons \(a\) and \(b\), the condition \(|a - b| \le p\) must hold. Additionally, if person \(a\) dislikes person \(b\), then person \(b\) cannot be seated immediately to the right of person \(a\). Given that the seat of person \(n\) is fixed, determine the number of valid seating arrangements for the remaining \(n-1\) persons.

inputFormat

The input begins with three integers \(n\), \(p\), and \(m\) where:

• \(n\) is the number of people,
• \(p\) is the maximum allowed absolute difference between the numbers on two adjacent seats, and
• \(m\) is the number of dislike relationships.

This is followed by \(m\) lines. Each of these lines contains two integers \(a\) and \(b\), indicating that person \(a\) dislikes person \(b\) (so \(b\) cannot be seated immediately to the right of \(a\)).

outputFormat

Output a single integer representing the number of valid seating arrangements.

sample

4 1 0

0