Vasilică a cumpărat un pachet de cărţi de joc mai special. Pachetul conţine A₁ cărţi cu valoarea 1, A₂ cărţi cu valoarea 2, ..., A_N cărţi cu valoarea N.
El se întreabă în câte moduri poate construi un şir format din toate cărţile din pachet astfel încât orice carte cu valoarea K+1 să fie precedată de cel puţin o carte cu valoarea K (1<=K<N).

Cerinţă

Să se detemine numărul de moduri in care se poate construi un şir format din toate cărţile din pachet astfel încât orice carte cu valoarea K+1 să fie precedată de cel puţin o carte cu valoarea K (1 <= K < N).

Date de intrare

Fişierul de intrare carti.in contine pe prima linie numarul natural N. Pe cea de a doua linie se afla N numere naturale separate prin spaţii A₁ A₂ ... A_N.

Date de ieşire

Fişierul de ieşire carti.out va contine pe o singura linie pe care va fi scris un număr natural reprezentând numarul de şiruri care respectă condiţiile din enunţ.

Restricţii

• 1 <= N <= 100
• 1 <= A₁+A₂+...+A_N <= 100

Exemple

carti.in	carti.out	Explicatie
2 2 2	3	Şirurile sunt:  1 1 2 2, 1 2 1 2, 1 2 2 1

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com