expression

Le but de votre programme est d'évaluer une expression à plusieurs variables et à coefficients entiers positifs pour une affectation entière positive donnée de ses variables. Chaque testcase consiste en plusieurs lignes. La première ligne contient un entier N compris entre 0 et 26. La ligne suivante est une chaîne de caractères E ne contenant pas d'espaces et représentant une expression mathématique : E contient des entiers positifs (compris entre 0 et 1.000.000.000), des lettres minuscules de l'alphabet latin (qui vont correspondre aux variables), des parenthèses (, ) et des opérateurs mathématiques +, *, et ^. Le nombre de lettres dans E n'est pas connu d'avance, en revanche le nombre de lettres distinctes dans E est exactement N. Ensuite, suivent N lignes de la "forme a=entier positif" compris entre 0 et 1.000.000.000, où "a" est une variable de E. Attention, E représente une expression mathématique valide, les exposants sont des entiers positifs "simples" (ce ne sont pas des expressions arithmétiques composées) et les priorités sont données uniquement par les parenthèses, ("1+2+3" ne peut pas apparaitre dans les testcases)

Une grammaire pour générer les expressions pourrait être:


expr -> base | (expr) | (expr+expr) | (expr*expr) | (expr^base)
base -> [a-z] | entier positif

Pour chaque testcase votre programme doit afficher le résultat du calcul de E modulo 1.000.000.007 après valuation de ses variables.

Input

0
(1+2)
0
(3+(5+6))
0
((2^3)+5)
2
(a+(b^2))
a=3
b=6
3
((x^y)+z)
x=5
y=6
z=2
8
((((((o^638022372)*(631416347*b))+f)+(((q^c)+(((q+y)^c)^c))^o))^k)^m)
b=942409124
c=884730203
f=352020689
k=719080959
m=978785428
o=163677341
q=276590098
y=374787159

Télécharger l'entrée

Output

3
14
13
39
15627
90770736

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.