16687번 - 기묘한 여행계획

휴학을 한 창수는 열심히 알바를 해서 B원을 모았다. 창수는 돈도 쌓였겠다, 홍준랜드로 여행을 가기로 결정했다.

홍준랜드는 N개의 여행지로 구성되어있으며, 각 여행지들은 2차원 격자판상에 존재한다. i 번째 여행지는 점 (x_i, y_i)로 표현된다.

홍준랜드의 특별한 규칙이 있는데, 여행지끼리 이동할 때 꼭 택시를 타야만 한다. 택시요금은 택시거리로 책정된다. 즉 임의의 여행지 s (x_s, y_s)에서 여행지 e (x_e, y_e)로 이동하는데 |x_s - x_e| + |y_s - y_e| 만큼의 비용이 든다. 또한 홍준랜드의 각 여행지 i, i+1 에 대해 x_i ≤ x_i+1 , y_i ≤ y_i+1 이 성립한다. (1 ≤ i < N) 단, 같은 점에 두 개이상의 여행지가 있는 경우는 없다. 그리고 홍준랜드의 택시는 출발지에서 택시에 탑승하자마자 경로상의 여행지를 볼 새도 없이 도착지에 도착한다.

창수는 B원 이하의 비용을 써서 N개의 여행지를 단 한 번씩 모두 방문하는 여행을 하고 싶어한다.

문득 창수는 이런 계획이 몇 가지나 존재하는지 궁금해졌다. 창수가 세울 수 있는 여행계획의 경우의 수를 1,000,000,007로 나눈 나머지를 구하시오.

첫 번째 줄에는 홍준랜드에 있는 여행지의 개수와 창수가 희망하는 최대 비용을 의미하는 두 정수 N과 B가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 60, 0 ≤ B ≤ 2,000)

그 이후 N개의 줄에 걸쳐 여행지의 위치가 주어진다. i 번째 줄에는 i 번째 여행지의 정보인 두 정수 x_i, y_i 가 공백으로 구분되어 주어진다. (|x_i| ≤ B,  |y_i| ≤ B)

가능한 여행 계획의 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.