题目描述
春河希望和偶像吾妻沙罗做好朋友。
矢逆一稀希望满足春河的愿望，于是每天都伪装成沙罗拍幸运自拍发送给春河。
但是有一天，自拍时不小心拍到了正在撬车的久慈悠，于是被久慈悠追杀。
当然，一稀也不希望春河识破他的伪装。
一共有 n 个平行世界，每个平行世界有一个人，1∼a 号平行世界这个人是一稀，a+1∼a+b 号平行世界是久慈，a+b+1∼n 号平行世界是春河。第 i 号平行世界的人一开始处于 (xi, yi) 这个位置。
每一分钟，位于 (x, y) 的人会移动到 (x−1,\ y),\ (x+1,\ y),\ (x,\ y−1),\ (x,\ y+1) 这四个点中的一个点。
m 分钟过后，由于因果律的影响，相同的人会移动到相同的位置，而不同的人最后移动到的位置是不同的。那么有多少种可能的方案？答案对 109+7 取模。
方案不同，当且仅当某个人最后的位置不同，或者存在一个人在两种方案中的移动路径不同。
输入格式
第一行四个整数 n, a, b, m，保证 a, b≥1 且 a+b<n。
接下来 n 行每行两个整数 xi, yi 表示第 i 个人的初始位置。
输出格式
一个整数表示答案。
输入输出样例
3 1 1 4
0 0
0 1
0 2
15974400
数据范围
对于 10% 的数据，n, m≤3。
对于 20% 的数据，n≤3，m≤20。
对于 40% 的数据，m≤20。
对于另外 20% 的数据，m, ∣xi∣, ∣yi∣≤100。
对于所有数据，满足 n, m, ∣xi∣, ∣yi∣≤1000。