Knights of the Round Table

K knights sit at seats 1..K around a circle. The first D distracted knights already sat (knight assigned seat A is on seat B). Each remaining knight enters, tries his own seat, and if it is taken walks clockwise to the first free seat. Count distinct final seatings over all entry orders of the remaining knights, modulo 10^9+7.

Several test cases. Each has K, D, then D lines with A and B meaning the knight assigned seat A sat on seat B.

For each test case, print the number of distinct final distributions modulo 10^9+7.