The first line contains N and K.
Each of the next N lines contains two integers li and ri. It is guaranteed that li<ri and all li,ri are distinct integers in the range 1…2N.
Output the answer, modulo 109+7.
Test case 2 satisfies N≤16.
Test cases 3-5 satisfy N≤1000, K=2.
Test cases 6-8 satisfy N≤1000.
For each T∈[9,16], test case T satisfies K=3+(T−9).