Bridge

Bridge

Solution

Tests

Between the two sides of one deep canyon a suspended bridge was built. The bridge was made using N pieces of wood connected by steel cables. We consider that the pieces of wood are numbered from 1 to N, starting from the side that we are on. In time, some pieces of wood have deteriorated, and others even disappeared. For crossing the bridge we know that:

-we can make only 1,2 or 3 units long steps

-the deteriorated pieces of wood are unsure and on them we can do only 1 unit long steps

-we can't step on one missing piece of wood

Task

Write a program that will determine the number of solutions for crossing the bridge.

Input format

The input file POD.IN has the following structure:

POD.IN	Significance
N k s₁ s₂ ... s_k h d₁ d₂ ... d_h	Number of pieces of wood Number of missing pieces of wood and their order numbers Number of deteriorated pieces of wood and their order numbers

Output format

The output file POD.OUT will contain the value –1 if it is not possible to cross the bridge, or the number of possibilities for crossing the bridge, if it is possible.

POD.OUT	Significance:
Nr	Number of possibilities

Constraints and observations:

3 <=N <=300

0 <=k, h <=N

{s₁,s₂,...,s_k} <= {2,...N}, {d₁,d₂,...,d_h} <= {1,2,...N};

{s₁,s₂,...,s_k} ^ {d₁,d₂,...,d_h}=ø

The number Nr has no more than 80 characters.

Example 1:		Example 2:		Example 3:
POD.IN	POD.OUT	POD.IN	POD.OUT	POD.IN	POD.OUT
5 0 0	24	10 2 2 7 1 5	48	6 2 2 4 1 3	-1

Time limit: 1 second/test .