题目描述

有 $n$ 只狼生活在无限整数网格上，第 $i$ 只狼初始位于 $(x_i,y_i)$。

接下来恰好进行 $m$ 轮移动。每一轮中，每只狼都必须移动到上下左右四个相邻格点之一，即从 $(x,y)$ 移动到 $(x+1,y)$、$(x-1,y)$、$(x,y+1)$ 或 $(x,y-1)$。

要求在第 $m$ 轮结束后，所有狼位于同一个格点。会合点可以任意选择。

求所有狼的移动方案总数，对 $1\,000\,000\,007$ 取模。两种方案只要至少有一只狼在某一轮选择的移动方向不同，就视为不同方案。

输入格式

第一行输入两个整数 $n,m$。

接下来 $n$ 行，每行输入两个整数 $x_i,y_i$。

输出格式

输出满足条件的移动方案数，对 $1\,000\,000\,007$ 取模。

数据范围

$2\le n\le 50$；$1\le m\le 100000$；$-100000\le x_i,y_i\le 100000$；所有初始位置两两不同。

样例 1

2 1
3 0
5 0

1

样例 2

3 2
0 0
2 0
4 0

4