Problem Iftode


Zgăbeață Iftode este fiul unui cârciumar din Văscăuți. Drept pedeapsă pentru proasta impresie lăsată în timpul inspecției domnului director, domnul pedagog a ordonat întregii clase să rezolve un exercițiu greu de matematică.
\(\\\)

Pedagogul și elevul Zgăbeață Iftode. Dem Rădulescu și Vasile Muraru în “Doi Vulpoi” (1983).
\(\\\)
Asupra unui număr natural X se pot efectua următoarele trei tipuri de operații:

  1. Adună 1 la X. Astfel, noua valoare a lui X va fi X + 1.
  2. Scade 1 din X. Astfel, noua valoare a lui X va fi X − 1. Operația este validă doar pentru X > 0.
  3. Înjumătățește X. Astfel, noua valoare a lui X va fi \(\frac{X}{2}\). Operația este validă doar pentru X par.

Oricare ar fi numărul inițial X este întotdeuna posibil ca prin operații de tipul celor de mai sus să se ajungă în cele din urmă la X = 0. Să notăm numărul minim de operații necesare cu \(c_{X}\). De exemplu, \(c_1 = 1\), deoarece putem efectua o operație de tipul 2 și să ajungem la 0, \(c_7 = 5\), deoarece putem efectua operațiile astfel: 7 → 8 → 4 → 2 → 1 → 0, iar \(c_6 = 4\), deoarece putem proceda astfel: 6 → 3 → 2 → 1 → 0.

Iftode a găsit într-o veche carte de matematică o metodă eficientă de calcul a lui \(c_X\), după cum urmează (se garantează că această metoda este corectă):

\( c_X = \left\{ \begin{array}{ll} 0 & X = 0 \\ 1 + c_{\frac{x}{2}} & X > 0 \text{ și par} \\ 3 & X = 3 \\ 1 + c_{X+1} & X ≠ 3, \text{impar și } \frac{X-1}{2} \text{ impar} \\ 1 + c_{X-1} & \text{ altfel} \end{array} \right.\)

Pedagogul le cere elevilor să calculeze suma \(S = \sum_{X=L+1}^{R} c_X\) pentru două numere L, R date. Răspunsul se vrea modulo 1 000 000 007. Mai rău, numerele L, R vă sunt puse la dispoziție in baza 2.

Date de intrare

Pe prima linie se găsește numărul L. Pe a doua linie se găsește numărul R. Numerele se dau în baza 2.

Date de ieșire

Se va afișa pe primul rând suma S, modulo 1 000 000 007.

Restricții

Subtask 1 (2 puncte)

  • \(0 ≤ L ≤ R < 2^{18}\)

Stubatsk 2 (7 puncte)

  • \(0 ≤ L ≤ R < 2^{60}\)

Subtask 3 (5 puncte)

  • \(0 ≤ L ≤ R < 2^{300}\)
  • \(R - L ≤ 10^5\)

Subtask 4 (7 puncte)

  • \(0 ≤ L ≤ R < 2^{300}\)

Subtask 5 (7 puncte)

  • \(0 ≤ L ≤ R < 2^{800}\)

Subtask 6 (8 puncte)

  • \(0 = L ≤ R < 2^{2 500}\)
  • R + 1 este putere de 2

Subtask 7 (7 puncte)

  • \(0 ≤ L ≤ R < 2^{2 500}\)

Subtask 8 (9 puncte)

  • \(0 = L ≤ R < 2^{100 000}\)
  • R + 1 este putere de 2

Subtask 9 (48 puncte)

  • \(0 ≤ L ≤ R < 2^{100 000}\)

Exemple

stdin

100
111

stdout

13

stdin

10110111110101
110000101010110

stdout

256512

Explicații

În primul exemplu L = 4 și R = 7. Avem că \(c_5 = 4, c_6 = 4, c_7 = 5\), a căror sumă este S = 13.
În al doilea exemplu L = 11765 și R = 24918. Suma cerută este \(S = \sum_{X=11766}^{24918} c_X = 256512\).

General info

ID: 98

Upload: liviu

Input: Console Input

Memory limit: 128MB/128MB

Time limit: 1s

Source: Lot 2021 Baraj 3 Seniori: Problema 3

Submissions

Special Submissions