Задача №111877. Энергичная черепаха
Дана сетка с \(N\) + 1 рядами и \(M\) + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (\(N\), \(M\)). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем \(T\) раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (\(N\), \(M\)). Так как это число может быть очень большим, выведите остаток от его деления на \(Z\).
В первой строке входного файла задается 5 целых чисел: \(N\), \(M\), \(K\), \(T\) и \(Z\) (\(1\) \(\le\) \(N\),\(M\) \(\le\) 300000, 0 \(\le\) \(K\), \(T\) \(\le\) 20, 1 \(\le\) \(Z\) \(\le\) \(10^9\)). В каждой из следующих \(K\) строк расположены координаты соответствующей клетки с ловушкой \(X\), \(Y\) (0 \(\le\) \(X\) \(\le\) \(N\), 0 \(\le\) \(Y\) \(\le\) \(M\)). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (\(N\), \(M\)) ловушек нет.
Выведите требуемое число.
1 1 1 0 100 0 1
1
2 2 0 0 10
6