Lewis, the Hatter, (a graduate of Oxford University) organizes the education system of Wonderland University. In Wonderland there are N students attending the school. Lewis noticed that all of them are very smart, so he wants to measure their Intellectual Quotient (IQ) and rank then, such that no two students had the same IQ and that all IQs are integers in the range from 1 to N.
In Wonderland, one student can be the tutor of many other students, and also be the disciple of many others. Let J be the smallest integer greater than I such that the IQ of student J is greater than the IQ of student I, the disciples of student I are all the students numbered from I + 1 to J - 1. If no such J exist we consider J to be equal to N + 1, note that student number I will not have any disciples when J = I + 1 or when I = N.
Knowing the number of disciples for every student, Lewis wants to compute the IQ of each student. However, there are several IQ assignations. Help him calculate the number of IQ assignations that he can find. As the answer could be large, output it modulo 109 + 7.
An input file for LP systems contains the following facts:
students(Number) containing the number of students.disciples(Number,Disciples) containing the student number and the number of disciples.The output should contain exactly one fact of the form solutions(S), where S is number of IQ assignations that he can find modulo 109 + 7.
Examples:
students(4).
disciples(1, 0).
disciples(2, 2).
disciples(3, 1).
disciples(4, 0).
Output: solutions(3) because the possible students IQs are the following: [1, 4, 3, 2], [2, 4, 3, 1], [3, 4, 2, 1].
students(4).
disciples(1, 0).
disciples(2, 2).
disciples(3, 1).
disciples(4, 1).
Output: solutions(0) because there are no possible assignments because the last student cannot
have one pupil.