Taxi

Seoul has N intersections numbered from 1 to N. Some intersections are connected by narrow one-way roads. In this road network, there is no route that starts from an intersection and returns to the same intersection, and no ordered pair of intersections is connected by more than one road.

Minsung picks up a passenger at intersection A, and the passenger wants to go to intersection B. During the drive, the passenger must visit all of the intersections C1, C2, ..., Ck for meetings. The order in which these intermediate intersections are visited does not matter.

Minsung noticed that there may be several routes satisfying these conditions. Count how many such routes exist.

The first line contains the number of intersections N (1 <= N <= 1,000) and the number of roads M (1 <= M <= 1,000,000).

Each of the next M lines contains the start and end intersections of one road.

After the road data, the input gives the starting intersection A, the destination intersection B, and the number K (0 <= K <= N - 2) of intermediate intersections that must be visited.

Then C1, C2, ..., Ck are given separated by spaces. The intermediate intersections do not include the start or destination, and no intermediate intersection appears more than once.

Print S, the number of routes satisfying the conditions. If no such route exists, print 0.

Inputs where S exceeds 2,000,000,000 are not given.