Trosu tilts

ID: tilts
Grūtība: 3/5
Laika limits: 1

Uzdevums

Trosu tilts sastāv no divām trosēm, kam pāri noteiktos attālumos piestiprināti N dēlīši. Uzskatīsim, ka dēlīši, sākot no viena krasta, ir sanumurēti ar naturāliem skaitļiem no 1 līdz N pēc kārtas.
Laika gaitā daži dēlīši ir stipri nodiluši, bet citi pat salūzuši.
Ir zināms, ka tiltu var veiksmīgi šķērsot, ja

Uzrakstiet programmu, kas nosaka, cik dažādos veidos iespējams pāriet pār tiltu, ja tas vispār ir iespējams!

 

Ievaddati

Teksta faila tilts.in pirmā rinda satur naturālu skaitli N - tilta dēlīšu skaitu(3<=N<=300) .
Faila otrajā rindā dots salūzušo dēlīšu apraksts formā k s1 s2 ... sk , kur k ir salūzušo dēlīšu skaits, bet si - salūzušā dēlīša numurs (1<=si<=N). Starp katriem diviem blakus skaitļiem ir viens tukšumsimbols.
Faila trešajā rindā dots nodilušo dēlīšu apraksts tādā pat formātā kā salūzušo dēlīšu apraksts.

 

Izvaddati

Teksta faila tilts.out vienīgajā rindā jāizvada viens vesels skaitlis - dažādo variantu skaits, kādā iespējams šķērsot tiltu. Zināms, ka visiem testa datiem dažādo variantu skaits ir skaitlis ar ne vairāk kā 80 cipariem.

 

Piemērs

tilts.intilts.out
5
0
0
24
tilts.intilts.out
10
2 2 7
1 5
48
tilts.intilts.out
6
2 2 4
1 3
0

 

Atsauces

Uzdevums izmantots Rumānijas informātikas olimpiādē 2002.gadā.
© 2001-2002 olimps! http://www.lio.lv/olimps/