Posloupnosti

Zadání

Mějme nějakou neprázdnou množinu M celých kladných čísel. Posloupnost celých kladných čísel nazveme M-vázanou, pokud absolutní hodnota rozdílu libovolných dvou sousedních prvků této posloupnosti je rovna některému prvku M.

Pro danou množinu M určete, kolik existuje navzájem různých M-vázaných posloupností délky N, které každý prvek množiny {1, 2, …, N} obsahují právě jednou.

Vstup

Na vstupu je textový soubor obsahující dva řádky. Na prvním řádku je zapsáno číslo N. Na druhém řádku je zapsána množina M tak, že nejprve je uvedena mohutnost M a potom jednotlivé prvky M. Všechny údaje na řádku jsou odděleny navzájem jednou mezerou. Pro zadané parametry platí:
|M| ≤ 8;
2 ≤ N ≤ 25;
Data jsou zadána korektně, není nutno je kontrolovat.

Výstup

Na výstupu je jediný řádek obsahující jediné číslo, které udává počet navzájem různých M-vázaných posloupností délky N obsahujících právě jednou každý prvek množiny {1, 2, …, N}. Počet je vždy menší než 10⁸.

Příklady

Příklad 1

Vstup

2
2 1 2

Výstup

Příklad 2

Vstup

3
2 3 5

Výstup

Příklad 3

Vstup

7
2 2 3

Výstup

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data