Procente

Definim o modificare procentuală de preț ca fiind o pereche $(c$, $p)$ formată dintr-un caracter $c \in \{‘+‘$, $‘-‘\}$ și un număr natural $p$. Dacă $c = ‘+‘$ atunci are loc o scumpire iar dacă $c = ‘-‘$ atunci are loc o ieftinire a unui preț, iar numărul $p$ reprezintă procentul de modificare a prețului.
Exemple de modificări procentuale de preț:

• $(+ 35)$ – reprezintă scumpirea unui preț cu $35\%$
• $(– 50)$ – reprezintă ieftinirea unui preț cu $50\%$

Unui preț inițial i se poate aplica o succesiune de $n$ modificări procentuale de preț obținându-se un preț final. Numim ciclu de preț de lungime $n$ o succesiune de $n$ modificări procentuale de preț, cu proprietatea că prețul final este egal cu prețul inițial.

Exemple de cicluri de preț :

• de lungime $n=2$: $(- 20)$, $(+ 25)$
• de lungime $n=3$: $(- 50)$, $(+ 25)$, $(+ 60)$

Cerință

Să se scrie un program care citește un număr natural $n$ și determină numărul de cicluri de preț de lungime n distincte ce conțin cel puțin o dată, o modificare procentuală cunoscută $(C$, $P)$.

Date de intrare

Fişierul de intrare procente.in conţine pe prima linie numărul natural $n$ și pe a doua linie un caracter $C \in \{‘+‘$, $‘-‘\}$, urmat de un număr natural $P$, despărțite printr-un spațiu, cu semnificaţia de mai sus.

Date de ieșire

Fişierul de ieşire procente.out va conţine pe prima linie numărul căutat.

Restricții și precizări

• $2 \leq n \leq 80$;
• $C \in \{‘+‘$, $‘-‘\}$
• Valoarea procentului $p$ în caz de scumpire este cuprinsă între $0$ și $100$ inclusiv.
• Valoarea procentului $p$ în caz de ieftinire este cuprinsă între $1$ și $99$ inclusiv.
• Două modificări procentuale de preț $(c_{1}$, $p_{1})$, $(c_{2}$, $p_{2})$ sunt diferite dacă $c_{1} \neq c_{2}$ sau $p_{1} \neq p_{2}$.
• Două cicluri de preț de lungime $n$ sunt distincte, dacă diferă prin cel puțin o modificare procentuală de preț.
• Două cicluri de preț de lungime $n$ ce conțin aceleași modificări procentuale, dar în altă ordine, sunt identice.
• Pentru $28\%$ din punctaj $n \leq 20$, pentru $60\%$ din punctaj $n \leq 40$, pentru $100\%$ din punctaj $n \leq 80$

Exemplul 1

procente.in

2
- 20

procente.out

1

Explicație

Există o singură succesiune de $2$ modificări procentuale de preț ce conține și o ieftinire cu $20\%$ care are prețul final egal cu prețul inițial. Această succesiune este $(- 20)$, $(+ 25)$.

Exemplul 2

procente.in

3
+ 25

procente.out

4

Explicație

Există patru succesiuni distincte de $3$ modificări procentuale de preț ce conțin cel puțin o scumpire cu $25\%$ care au prețul final egal cu prețul inițial. Aceste succesiuni sunt:

• $(- 50)$, $(+ 25)$, $(+ 60)$
• $(- 36)$, $(+ 25)$, $(+ 25)$
• $(- 60)$, $(+ 25)$, $(+ 100)$
• $(- 20)$, $(+ 25)$, $(+ 0)$