Городские олимпиады/Общегородские тренировки/2018, 24 июня


8. Вариативность

Ограничение по времени: 2 с.
Ограничение по памяти: 256 МБ

Витя ходит на работу пешком. Ему нравится варьировать свой маршрут, добираясь до работы то так, то эдак. Ходит Витя только по дорожкам, не срезая путь через газоны и жилые кварталы. Землю, в масштабах города, можно считать плоскостью. Всякая дорожка соединяет пару перекрёстков, которые можно условно считать точками на этой плоскости с известными координатам. Дорожки являются отрезками прямых линий.

И дом Вити, и место, где он работает, располагаются на перекрёстках.

Конечно, можно придумать целую кучу маршрутов, чтобы дойти от дома Вити до его работы (если он согласится ходить кругами, то количество таких маршрутов и вовсе станет бесконечным). Однако же, Виктор хочет дойти до работы за разумное время, поэтому поставил себе дополнительное условие: он может пройти по дорожке в том лишь случае, если на протяжении всего пути по ней он будет приближаться к своей работе. Мерой близости при этом служит декартово расстояние от положения Вити до перекрёстка, около которого располагается его работа.

Вите стало интересно, как много различных маршрутов он может проложить по известным ему дорожкам. По его ощущениям, число может получиться довольно большим, поэтому требуется найти лишь остаток от деления этого числа на 1000.

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

В первой строке входных данных содержится одно целое число n — количество перекрёстков (2 \leqslant n \leqslant 10^5).

Последующие n строк содержат по паре целых чисел x_i и y_i, разделённых пробелом – координаты перекрёстков (-10^9 \leqslant x_i, y_i \leqslant 10^9, 1 \leqslant i \leqslant n). Гарантируется, что координаты всех перекрёстков попарно различны.

Следующая строка содержит целые числа s и f, разделённые пробелом — номер перекрёстка, около которого Витя живёт, и номер перекрёстка, около которого он работает, соответственно (1 \leqslant s, f \leqslant n, s \neq f).

Следующая строка содержит одно целое число m — количество дорожек (1 \leqslant m \leqslant min(n(n-1) / 2, 10^5)).

Последующие m строк содержат по паре целых чисел u_i и v_i, разделённых пробелом – номера перекрёстков, соединяемых i-й дорожкой (1 \leqslant u_i, v_i \leqslant n, u_i \neq v_i, 1 \leqslant i \leqslant m). Гарантируется, что каждую пару перекрёстков соединяет не более одной дорожки.

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

Вывести одно целое число — количество вариантов построения маршрутов для Вити по модулю 1000.

Примеры
Стандартный вводСтандартный вывод
4
-2 2
2 2
-2 -2
2 -2
1 4
6
1 2
1 4
1 3
4 2
4 3
3 2
3
Примечания

Если две дорожки пересекаются, но не в перекрёстке, с которым они обе соединены, то перейти с одной дорожки на другую нельзя. Считайте, что в этом случае одна дорожка проходит по мостику над другой. Схема дорожек из примера, в таком случае, выглядит следующим образом:

image