Non-Adjacent Placements in a Grid with Obstacles

You are given an integer grid of size \(n \times m\). Some cells in the grid are marked as obstacles. You are also given an integer \(k\). Your task is to select exactly \(k\) cells from the non-obstacle cells such that no two selected cells share a common edge.

More formally, you are given integers \(n, m, t, k\) where \(t\) is the number of obstacles, followed by \(t\) pairs of integers. Each pair \((x,y)\) represents the coordinates of an obstacle (1-indexed). Let \(G\) be the grid where the obstacles are forbidden positions. Count the number of ways to choose exactly \(k\) cells from the allowed positions of \(G\) such that for any two chosen cells \((i_1, j_1)\) and \((i_2, j_2)\), it holds that \[ |i_1-i_2|+|j_1-j_2| \neq 1. \]

Since the answer can be large, output it modulo \(10^9+7\).

inputFormat

The first line contains four integers \(n, m, t, k\) \( (1 \leq n, m \leq 10,\ 0 \leq t \leq n \times m,\ 0 \leq k \leq n \times m)\).

The next \(t\) lines each contain two integers \(x\) and \(y\) (1-indexed) representing the coordinates of an obstacle.

outputFormat

Output a single integer, the number of valid ways to choose exactly \(k\) non-adjacent, non-obstacle cells, modulo \(10^9+7\).

sample

2 3 1 2
1 2

6