Trosu tilts

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

• katra soļa garums ir 1, 2 vai 3,
• katrs nodilušais dēlītis nav īsti drošs un uz tā drīkst uzkāpt un iet tālāk tikai ar soli garumā 1,
• nedrīkst uzkāpt ne uz viena salūzušā dēlīša.

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 s₁ s₂ ... s_k , kur k ir salūzušo dēlīšu skaits, bet s_i - salūzušā dēlīša numurs (1<=s_i<=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.in	tilts.out
5 0 0	24
tilts.in	tilts.out
10 2 2 7 1 5	48
tilts.in	tilts.out
6 2 2 4 1 3	0

Atsauces