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 ∊ {"1", "2"; "200"; ...})
• e = "[e1,e2]" sau e = "(e1,e2)", unde e1, e2 sunt (sub-)expresii. Aici, (•, •) semnifică cel mai mare
  divizor comun a două numere, iar [•,•] semnifică cel mai mic multiplu comun a 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 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

Cerința

Dându-se o expresie e și două numere naturale a, b, să se calculeze eval(e, a) + eval(e, a+1) + ... + eval(e, b). Rezultatul se va afișa modulo 1.000.000.007.

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

• 1 ≤ a ≤ b ≤ 250.000, 1 ≤ |e| ≤ 2.000.000, 0 ≤ max(e) ≤ 250.000, unde |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

(4, 6) = 2.

Exemplul 2:

expresii.in

[x,6]
1 6

expresii.out

66

Explicație

[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

Răspunsurile pentru fiecare valoare din interval sunt 4, 2, 10, 2, 16, 2 (în această ordine).