expresii

Definim o expresie ca fiind un șir de caractere $e$ care respectă una dintre următoarele:

• $e =$ x;
• $e$ reprezintă un număr natural (constantă); (ex. $e \in \{$1$,$ 2$,$ 200$, \dots\}$)
• $e = [e_1, e_2]$ sau $e = (e_1, e_2)$, unde $e_1$, $e_2$ sunt (sub-)expresii. Aici, $(\cdot, \cdot)$ semnifică cel mai mare divizor comun al două numere, iar $[\cdot, \cdot]$ semnifică cel mai mic multiplu comun al două numere. De exemplu, avem că $(6, 8) = 2$, $[6, 8] = 24$.

De exemplu, x, 13, (5,2), [3,[x,(14,1)]], [x,x] sunt expresii, pe când 0, (5, 2, 3), [x, 2) nu sunt expresii. Observați că expresiile nu conțin niciodată spații.

Pentru o expresie $e$ dată și un număr natural pozitiv $a$, definim $\textit{eval}(e, a)$ ca fiind rezultatul evaluării expresiei $e$, unde tuturor aparițiilor lui $x$ le vor fi asociate valoarea $a$. De exemplu:

$eval($([x,3],[x,2])$, 10) =$ ([10,3],[10,2]) $=$ (30,10) $=$ 10

$eval($(6,14)$, 5) =$ (6, 14) $=$ 2

$eval($x$, 12) =$ 12

Dându-se o expresie $e$ și două numere naturale $a, b$, să se calculeze $eval(e, a) + eval(e, a + 1) + \ldots + eval(e, b)$.

Rezultatul se va afișa modulo $10^9 + 7$.

Date de intrare

Fișierul de intrare expresii.in conține pe prima linie o expresie $e$. Pe a doua linie se găsesc numerele $a, b$, separate prin spațiu.

Date de ieșire

Fișierul de ieșire expresii.out va conține un număr întreg reprezentând valoarea cerută.

Restricții și precizări

• În tabelul ce urmează, $|e|$ reprezintă lungimea expresiei $e$ (numărul de caractere), iar $\max(e)$ reprezintă constanta de valoare maximă din $e$ (sau $0$, dacă $e$ nu conține constante).

Exemplul 1

expresii.in

(x,6)
4 4

expresii.out

2

Explicație

Pentru primul exemplu, $(4, 6) = 2$.

Exemplul 2

expresii.in

[x,6]
1 6

expresii.out

66

Explicație

Pentru al doilea exemplu, $[1, 6] + [2, 6] + [3, 6] + [4, 6] + [5, 6] + [6, 6] = 6 + 6 + 6 + 12 + 30 + 6 = 66$.

Exemplul 3

expresii.in

(12,(x,(8,6)))
3 6

expresii.out

6

Exemplul 4

expresii.in

([x,3],[x,2])
10 10

expresii.out

10

Exemplul 5

expresii.in

[([(x,5),2],[12,5]),(x,16)]
28 33

expresii.out

36

Explicație

Pentru ultimul exemplu, răspunsurile pentru fiecare valoare din interval sunt $4, 2, 10, 2, 16, 2$ (în această ordine).

Atenție! Exemplele $2$, $3$, $4$ și $5$ nu respectă constrângerile subtask-ului $1$. Exemplele $2$, $4$ și $5$ nu respectă constrângerile subtask-ului $2$. Exemplele $2$, $3$ și $5$ nu respectă constrângerile subtask-ului $6$.