Definim o modificare procentuală de preț ca fiind o pereche (c p) formată dintr-un caracter din {‘+‘,‘-‘} ș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ța

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 din {‘+‘,‘-‘}, 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 ≤ n ≤ 80
• C din {‘+‘,‘-‘}
• 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ț (c1 p1), (c2 p2) sunt diferite dacă c1≠c2 sau p1≠p2
• 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 ≤ 20, pentru 60% din punctaj n ≤ 40, pentru 100% din punctaj n ≤ 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).