Balances equilibrades V45017

Donats $n$ pesos, hem de col·locar-los en una balança, un rere l’altre, de manera que en cap moment el plat de la dreta tingui més pes que el de l’esquerra. Us demanem que calculeu el nombre de maneres que hi ha de fer-ho.

Per exemple, si $n=3$ i els pesos són $\{1,2,4\}$, algunes solucions possibles són:

$$(1e,2e,4e),(2e,1e,4e), (2e,4e,1d), (2e,1d,4e), (4e,1d,2d), \cdots$$

on $1e$ significa que posem el pes $1$ al plat de l’esquerra, mentre que $2d$ significa que posem el pes $2$ al plat de la dreta. Recordem, com es veu a l’exemple, que l’ordre en el que posem els pesos importa i que, per tant, $(2e,4e,1d)$ i $(2e,1d,4e)$ són dues solucions diferents.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de pesos $n$ seguit dels $n$ diferents pesos, tots entre 1 i $10^6$. Podeu assumir que $1 \le n \le 8$.

Sortida

Per cada cas, escriviu el nombre de maneres correctes de col·locar els pesos a la balança. Aquest nombre mai serà més gran que $10^7$.