There are variables and requirements. Requirements are represented as , meaning that the variable must be less than or equal to the variable.
Your task is to assign non-negative numbers smaller than to each variable and then calculate the number of different assignments satisfying all requirements. Two assignments are different if and only if at least one variable is assigned to a different number in both assignments. Print your answer modulo .
Input Format
The first line contains space-separated integers, and , respectively. Each of the subsequent lines contains space-seperated integers describing the respective and values for an requirement.
Constraints
Output Format
Print your answer modulo .
Sample Input 0
6 7
1 3
0 1
2 4
0 4
2 5
3 4
0 2
Sample Output 0
1000
Explanation 0
There are variables and requirements.
Let the variables be in the array .
Requirements are -
One of the assignments is -
Similarly there are assignments possible.
Result = .