There is a huge blanket on your bed but unfortunately it has N stains. You cover them using 
a single, rectangular silk cloth. The silk is expensive, which is why the rectangular piece needs to have the least area as possible. You love this blanket and decide to minimize the area covering the  stains. You buy some cleaning liquid to remove the stains but sadly it isn't enough to clean all of them. You can just remove exactly K stains. The rest of the stains need to be covered using a single, rectangular fragment of silk cloth.

Let X denote the area of the smallest possible silk cloth that may cover all the stains originally. You need to find the number of different ways in which you may remove K stains so that the remaining N-K stains can be covered with silk of area strictly less than X (We are looking for any configuration that will reduce the cost).

Assume that each stain is a point and that the rectangle is aligned parallel to the axes.  

Input Format

The first line contains two integers N (1<=N<=1000) and K (0<=K<=N). 
Next follow N lines, one for each stain. Each line contains two integers in the form 'X Y', (0<=X,Y<100000), the coordinates of each stain into the blanket. Each pair of coordinates is unique.

Output Format

Output a single integer. The remainder of the division by 1000000007 of the answer.

Sample Input
5 2
0 1
3 3
2 0
0 3
2 3

Sample Output
8

Explanation

We can clean two spots. So removing any of the following set of stains will lead us to a conbination that will need less amount of silk.(The numbers refer to the indices of the stains in the input and they begin from 1).

1, 4
2, 1
2, 3
2, 4
2, 5
3, 1
3, 4
3, 5

So there are 8 ways.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


from functools import reduce

def choose(n, k):
	k = min(n - k, k)
	if k < 0:
		return 0
	if k == 0:
		return 1
	mult = lambda x, y: x * y
	num = reduce(mult, range(n, n - k, -1))
	den = reduce(mult, range(1, k + 1))
	return num // den
(N, K) = (int(x) for x in input().split(' '))
(x, y) = (int(x) for x in input().split(' '))
left = right = x
down = up = y
stains = [(x, y)]
sides = [1] * 4
for i in range(1, N):
	(x, y) = (int(x) for x in input().split(' '))
	stains.append((x, y))
	if x < left:
		left = x
		sides[1] = 1
	elif x > right:
		right = x
		sides[3] = 1
	elif x == left:
		sides[1] += 1
	elif x == right:
		sides[3] += 1
	if y < down:
		down = y
		sides[0] = 1
	elif y > up:
		up = y
		sides[2] = 1
	elif y == down:
		sides[0] += 1
	elif y == up:
		sides[2] += 1
corners = [False] * 4
for (x, y) in stains:
	if (x, y) == (left, down):
		corners[0] = True
	elif (x, y) == (left, up):
		corners[1] = True
	elif (x, y) == (right, up):
		corners[2] = True
	elif (x, y) == (right, down):
		corners[3] = True

def perms(p, l, start=0):
	if start == len(p) or l == 0:
		yield ()
		return
	for k in range(start, len(p) - l + 1):
		for perm in perms(p, l - 1, k + 1):
			yield ((p[k],) + perm)
big = 10 ** 9 + 7
ways = 0
if (right - left) * (up - down) == 1:
	corners = [False] * 4
	sides = []
	ways = 1 if N <= K else 0
elif right - left == 1:
	corners = [False] * 4
	sides = sides[::2]
elif up - down == 1:
	corners = [False] * 4
	sides = sides[1::2]
else:
	c = [0] * 16
	if corners[0]:
		c[3] += 1
		c[7] += 1
		c[11] += 1
		c[15] += 1
	if corners[1]:
		c[6] += 1
		c[7] += 1
		c[14] += 1
		c[15] += 1
	if corners[2]:
		c[12] += 1
		c[13] += 1
		c[14] += 1
		c[15] += 1
	if corners[3]:
		c[9] += 1
		c[11] += 1
		c[13] += 1
		c[15] += 1
for l in range(1, len(sides) + 1):
	sign = 1 if l & 1 else -1
	for perm in perms(range(4), l):
		s = sum((sides[i] for i in perm))
		s -= c[sum(map(lambda x: 2 ** x, perm))]
		ways += sign * choose(N - s, K - s)
print(ways % big)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


import math
import os
import random
import re
import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import math
import os
import random
import re
import sys

def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


def stain_combos(n, k):
	p = 1000000007
	if k < 0:
		return 0
	out = 1
	for i in range(n - k + 1, n + 1):
		out = out * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	denom = pow(denom, p - 2, p)
	return out * denom % p

def solve(n, k, stains):
	print(size_decrease(stains, k))
from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
	min_x = min([p.x for p in stains])
	max_x = max([p.x for p in stains])
	min_y = min([p.y for p in stains])
	max_y = max([p.y for p in stains])
	top = {p for p in stains if p.x == min_x}
	bot = {p for p in stains if p.x == max_x}
	left = {p for p in stains if p.y == min_y}
	right = {p for p in stains if p.y == max_y}
	out = 0
	for i in range(1, 5):
		for sides in combinations([top, bot, left, right], i):
			removed = reduce(lambda x, y: x.union(y), sides)
			length = len(removed)
			out += (-1) ** (i + 1) * stain_combos(len(stains) - length, k - length)
	return out % 1000000007
from collections import namedtuple
point = namedtuple('point', ['x', 'y'])
(n, k) = [int(x) for x in input().split(' ')]
stains = []
for _ in range(n):
	stains.append(point(*[int(number) for number in input().split(' ')]))
solve(n, k, stains)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)


import sys
p = []
prime = 1000000007
q = sys.stdin.readline().split()
n = int(q[0])
k = int(q[1])
minx = 100000
maxx = 0
miny = 100000
maxy = 0
for i in range(n):
	w = sys.stdin.readline().split()
	a = int(w[0])
	b = int(w[1])
	p.append((a, b))
	minx = min(a, minx)
	maxx = max(a, maxx)
	miny = min(b, miny)
	maxy = max(b, maxy)

def ext_euclid(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = ext_euclid(b, a % b)
	return (y, x - a // b * y)

def comp(n, k):
	if k < 0 or n < k:
		return 0
	if n - k < k:
		k = n - k
	result = 1
	for t in range(n - k + 1, n + 1):
		result = result * t % prime
	divide = 1
	for t in range(1, k + 1):
		divide = divide * t % prime
	u = ext_euclid(prime, divide)[1]
	while u < 0:
		u += prime
	result = result * u % prime
	return result

def checker(p, x0, x1, y0, y1):
	return p[0] == x0 or p[0] == x1 or p[1] == y0 or (p[1] == y1)

def counter(x0, x1, y0, y1):
	result = 0
	for i in range(n):
		if checker(p[i], x0, x1, y0, y1):
			result += 1
	return result
answer = 0
m = counter(-1, -1, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, -1, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, -1, -1)
answer = answer + comp(n - m, k - m)
m = counter(-1, -1, miny, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, miny, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(-1, maxx, -1, maxy)
answer = answer - comp(n - m, k - m)
m = counter(minx, maxx, -1, -1)
answer = answer - comp(n - m, k - m)
m = counter(minx, -1, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(-1, maxx, miny, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, -1)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, -1, maxy)
answer = answer + comp(n - m, k - m)
m = counter(minx, maxx, miny, maxy)
answer = answer - comp(n - m, k - m)
while answer < 0:
	answer += prime
print(answer % prime)