28129번 - 2022 APC가 어려웠다고요?

2022 APC는 출제진들의 생각보다 어려웠다고 한다. 난이도의 조절을 위해 2023 APC의 출제자 현빈이는 문제 난이도에 대한 가이드라인을 만들었다. 2023 APC에는 $N$개의 문제가 출제될 예정이다. 각 문제는 순서대로 $1$번부터 $N$번까지의 번호를 가진다.

현빈이가 만든 난이도 가이드라인에는 두 가지 규칙이 있다.

• $i$번 문제의 난이도 $D_{i}$는 $a_{i}\leq D_{i}\leq b_{i}$를 만족하는 정수다.
• 인접한 문제의 난이도 차이는 $K$이하다. 다시 말해 모든 $i$에 대해 $|D_{i}-D_{i+1}|\leq K$를 만족한다.

현빈이를 위해 난이도 가이드라인의 규칙을 준수하면서 $N$개 문제의 난이도를 결정하는 방법의 수를 구해주자.

첫째 줄에 $N$과 $K$가 주어진다. $(1\leq N\leq 3\,000; 0\leq K \leq 3\,000)$

둘째 줄부터 $N$줄에 걸쳐 $a_{i}$와 $b_{i}$가 공백으로 구분되어 주어진다. $(1\leq a_{i} \leq b_{i} \leq 3\,000)$

입력으로 주어지는 모든 값은 정수다.

문제의 조건에 맞게 $N$개 문제의 난이도를 결정하는 방법의 수를 $10^{9}+7$로 나눈 나머지를 출력하시오.

죄성함다.