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 .
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.