Pasiyans

Bütün məsələləri yarışmada həll etdikdən sonra kompüterdə pasyans oynamağa qərar verdiniz. Sizin $N$ ədəd oyun kartınız var, bu kartlar $1$-dən $N$-ə qədər nömrələnib. Oyun sahəsində isə $M$ hücrə mövcuddur və bu hücrələr soldan sağa $1$-dən $M$-ə qədər nömrələnib.

Tapşırığınız — hər kartı bir hücrəyə yerləşdirməkdir, aşağıdakı qaydalara əməl edərək:

• Kart $1$ kart $2$-dən dəqiq D_1 hücrə sola və ya dəqiq D_1 hücrə sağa yerləşdirilməlidir.

• Kart $2$ kart $3$-dən dəqiq D_2 hücrə sola və ya dəqiq D_2 hücrə sağa yerləşdirilməlidir.

• ...

• Kart $N$ kart $1$-dən dəqiq D_N hücrə sola və ya dəqiq D_N hücrə sağa yerləşdirilməlidir.

Pasyansı neçə müxtəlif şəkildə düzəldə biləcəyinizi müəyyənləşdirməlisiniz. Qeyd edək ki, bir hücrədə istənilən sayda kart yerləşdirilə bilər.

Giriş

Birinci sətirdə iki tam ədəd $N$ və $M$ boşluqla ayrılmış şəkildə verilir.İkinci sətirdə $N$ tam ədəd D_1, D_2, \ldots, D_N boşluqla ayrılmış şəkildə verilir.

Çıxış

Kartları qaydalara uyğun yerləşdirməyin müxtəlif yollarının sayını çap edin.

Məhdudiyyətlər

• 2 < N < 36

• 1 < M < 1\ 000\ 000

• 1 < D_j < 10\ 000, hər $j$ üçün.

Qeyd

Birinci nümunədə mümkün düzülüşlər:

• $\{1\}$ — $\{5\}$ — $\{4\}$ — $\{2\}$ — $\{3\}$

• $\{5\}$ — $\{1,4\}$ — $\{\}$ — $\{3\}$ — $\{2\}$

• $\{1,4\}$ — $\{5\}$ — $\{3\}$ — $\{2\}$ — $\{\}$

• $\{\}$ — $\{1,4\}$ — $\{5\}$ — $\{3\}$ — $\{2\}$

• $\{3\}$ — $\{2\}$ — $\{4\}$ — $\{5\}$ — $\{1\}$

• $\{2\}$ — $\{3\}$ — $\{\}$ — $\{1,4\}$ — $\{5\}$

• $\{\}$ — $\{2\}$ — $\{3\}$ — $\{5\}$ — $\{1,4\}$

• $\{2\}$ — $\{3\}$ — $\{5\}$ — $\{1,4\}$ — $\{\}$