На
плане города, в котором Петя Булочкин работает таксистом, есть N (1<=N<=1000) площадей, пронумерованных от
1 до N (в
дальнейшем, будем отождествлять площадь с ее номером). Некоторые площади
соединены дорогами. Дороги эти настолько узкие, что на них введено
одностороннее движение. По своему опыту Петя знает, что, выехав с
какой-нибудь площади и проехав несколько дорог, невозможно приехать опять
на эту же площадь. Нет двух дорог, соединяющих одну и ту же пару площадей.
Дороги пересекаются только на площадях.
Один
раз на площади A
Петя подобрал пассажира, который попросил довезти его до площади B, причем по дороге
остановиться на площадях C1, C2, …, Ck (на них пассажира
будут ждать знакомые). Порядок посещения промежуточных площадей для
пассажира не важен. «Сколько же денег взять с него?» - задумался Петя. Он
решил взять с пассажира столько рублей, сколько существует различных
маршрутов от площади A до площади B, проходящих через C1, C2, …, Ck.
Задание. По введенной информации
о дорогах в городе, а также перекресткам A, B, C1, C2, …, Ck определить, сколько
существует маршрутов от площади A до площади B, проходящих через C1, C2, …, Ck.
Ввод. Первая строка ввода
содержит числа N
– количество площадей и M – количество дорог. В следующие
M строках
находятся описания дорог. Каждая из этих строк содержит по два числа –
начальную и конечную площадь для дороги. Обратите внимание, что проехать
по дороге в обратном направлении (от конечной площади к начальной) нельзя:
движение одностороннее. В следующей строке будут числа A – начальная площадь, B – конечная площадь и
K – количество
промежуточных площадей. И, наконец, следующие K строк будут содержать числа
C1,
C2, …,
Ckпо одному в строке. Среди чисел A, B, C1, C2, …, Ck нет одинаковых.
Вывод. Вы должны вывести
единственное число S – количество маршрутов от
площади A до
площади B,
проходящих через C1, C2, …, Ck. Заметим, что в
случае отсутствия таких маршрутов S должно быть равно 0. Входные
данные будут таковы, что S не превысит 2000000000.