E. Исследовательский зонд
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

К сожалению, в этой задаче не удалось написать достаточно короткую формальную постановку, поэтому пришлось придумать легенду.

Исследовательский зонд, наконец, достиг поверхности Марса и готов выполнить свою миссию. К сожалению, из-за сбоя навигационной системы, зонд приземлился не в той точке, в которой планировалось.

Участок, на котором высадился зонд, можно представить в виде клетчатого поля, состоящего из n строк и m столбцов. Будем обозначать через (r, c) клетку, расположенную в строке r и столбце c. Из каждой клетки зонд может продолжить движение только в клетки по соседству с текущей по стороне.

Зонд высадился в клетке с координатами (1, 1) и должен отправиться в клетку с координатами (n, m). Для этого зонд выберет произвольный кратчайший маршрут, соединяющий начальную и конечную клетки. Каждый возможный маршрут зонд выберет с равной вероятностью.

В грузовом отсеке зонда находится батарея, которая понадобится зонду для проведения исследований в конечной точке его маршрута. Изначально заряд батареи равен s единицам энергии.

В некоторых клетках данного поля находятся аномалии. Каждый раз, когда зонд оказывается в клетке с аномалией, батарея теряет половину своего заряда, округлённую вниз, то есть если до попадания в аномалию заряд был равен x, то после попадания он будет равен .

Пока зонд перебирает все возможные маршруты своего путешествия, посчитайте математическое ожидание заряда батареи в момент, когда робот достигнет клетки (n, m). Если в клетках (1, 1) и (n, m) также есть аномалии, то они тоже изменяют заряд батареи.

Входные данные

Первая строка входных данных содержит четыре целых числа n, m, k и s (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 2000, 1 ≤ s ≤ 1 000 000) — количество строк и столбцов поля, количество клеток с аномалиями и начальный заряд батареи.

Следующие k строк содержат по два числа ri и ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) — координаты клетки, содержащей аномалию. Гарантируется, что никакая клетка не встречается во входном файле более одного раза.

Выходные данные

Ответ всегда можно представить в виде несократимой дроби . Выведите единственное число, равное P·Q - 1 по модулю 109 + 7.

Примеры
Входные данные
3 3 2 11
2 1
2 3
Выходные данные
333333342
Входные данные
4 5 3 17
1 2
3 3
4 1
Выходные данные
514285727
Входные данные
1 6 2 15
1 1
1 5
Выходные данные
4
Примечание

В первом примере зонд может выбрать один из шести маршрутов:

  1. , после прохождения клетки (2, 3) заряд становится равным 6.
  2. , после прохождения клетки (2, 3) заряд становится равным 6.
  3. , заряд батареи остаётся равным 11.
  4. , после прохождения клеток (2, 1) и (2, 3) заряд становится равным сначала 6, а затем 3.
  5. , после прохождения клетки (2, 1) заряд становится равным 6.
  6. , после прохождения клетки (2, 1) заряд становится равным 6.

Математическое ожидание заряда батареи в конце пути в данном случае считается по формуле: .

Таким образом, P = 19, а Q = 3.

3 - 1 по модулю 109 + 7 равно 333333336.

19·333333336 = 333333342 (mod 109 + 7)