시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 49 6 5 13.514%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3 20
1 1
3 5
9 7

예제 출력 1

4
  • 1번 여행지 -> 2번 여행지 -> 3번 여행지 순서로 방문하면 14만큼의 비용이 든다.
  • 1번 여행지 -> 3번 여행지 -> 2번 여행지 순서로 방문하면 22만큼의 비용이 든다.
  • 2번 여행지 -> 1번 여행지 -> 3번 여행지 순서로 방문하면 20만큼의 비용이 든다.
  • 2번 여행지 -> 3번 여행지 -> 1번 여행지 순서로 방문하면 22만큼의 비용이 든다.
  • 3번 여행지 -> 1번 여행지 -> 2번 여행지 순서로 방문하면 20만큼의 비용이 든다.
  • 3번 여행지 -> 2번 여행지 -> 1번 여행지 순서로 방문하면 14만큼의 비용이 든다.