procente

Definim o modificare procentuală de preț ca fiind o pereche $(C, P)$ formată dintr-un caracter $c \in \set{+,-}$ ș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 \set{+,-}$, 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 \set{+,-}$
• 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)$.